Network Lasso Bandits

Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-13 16:16:09

Abstract: We consider a multi-task contextual bandit setting, where the learner is given a graph encoding relations between the bandit tasks. The tasks' preference vectors are assumed to be piecewise constant over the graph, forming clusters. At every round, we estimate the preference vectors by solving an online network lasso problem with a suitably chosen, time-dependent regularization parameter. We establish a novel oracle inequality relying on a convenient restricted eigenvalue assumption. Our theoretical findings highlight the importance of dense intra-cluster connections and sparse inter-cluster ones. That results in a sublinear regret bound significantly lower than its counterpart in the independent task learning setting. Finally, we support our theoretical findings by experimental evaluation against graph bandit multi-task learning and online clustering of bandits algorithms.

Main paper: 
 introduction: 
 Online commercial websites aim to properly recommend their products to their customers, and the performance of these recommendations depends on the knowledge of users' preferences. Unlike traditional collaborative-filtering-based methods [Su and Khoshgoftaar, 2009] , such knowledge is initially unavailable. Therefore, the online recommender systems need to recommend various items to the users and observe their ratings to explore their preferences. At the same time, the recommender system should be able to recommend items that attract users' attention and receive high ratings by exploiting the learned knowledge. The contextual bandits frameworks [Li et al., 2010] have been popularly used to formalize and address this exploration-exploitation trade-off.However, the classical form of contextual bandits [Li et al., 2010 , Chu et al., 2011 , Abbasi-Yadkori et al., 2011] ignores the availability of social networks amongst users and solves the problem for each user separately. Consequently, such algorithms have some drawbacks when applied to problems with a large number of users. First, such a large number hinders the computational efficiency of such algorithms. Second, the partial feedback of the bandit settings exposes the algorithms to have weak estimations and impair their decision-making ability [Yang et al., 2020] . Consequently, to improve bandit algorithms' performance for large-scale applications, structural assumptions that link the different users are usually integrated within bandit algorithms [Cesa-Bianchi et al., 2013 , Gentile et al., 2014 , Li et al., 2019 , Herbster et al., 2021] .The papers of Cesa-Bianchi et al. [2013] , Yang et al. [2020] attempt to integrate the prior knowledge of social networks into their contextual bandit algorithms. Both papers proposed UCB-style algorithms and exhibited the importance of using the social network graph to achieve lower regrets using Laplacian regularization. Consequently, both methods promote smoothness among the preference vectors of users in order to transfer the collected information between them. However, the Laplacian regularization does not account for the smoothness heterogeneity introduced by a piecewise constant behavior over the graph [Wang et al., 2016] . On the other hand, algorithms of online clustering of bandits [Gentile et al., 2014 , Li et al., 2019] start from a graph and gradually add or remove edges to Submitted to 38th Conference on Neural Information Processing Systems (NeurIPS 2024). Do not distribute.form clusters as connected components. However, their clustering can cause overconfidence in the constructed clusters, potentially leading to error accumulation.In this paper, we assume access to a graph encoding relations between bandit tasks, and that the task parameter vectors are piecewise constant over the graph. That means that tasks form clusters. We propose an algorithm that integrates the prior knowledge of the piecewise constant structure to update tasks rather than finding the clusters explicitly. That way, we mitigate the limitations mentioned above: the piecewise constant smoothness is naturally integrated into our regularizer, and we do not estimate the clusters so our algorithm does not suffer from overconfidence drawbacks.More precisely, we provide the following contributions• We analyze an instance of the Network Lasso problem [Hallac et al., 2015] , where every vertex's preference vector is estimated using data generated during the interaction between users and the bandit. We provide the first oracle inequality in this setting and link it to fundamental quantities characterizing the relation between the graph and the true preference vectors of the users. Our result relies on our novel restricted eigenvalue (RE) condition, which we assume for our setting.This result is of independent interest and can be applied to independently generated data as a special case.• We prove how the empirical multi-task Gram matrix of the data inherits the RE condition from its true counterpart. Both this result and the previous one depend on the sparsity of inter-cluster connections and the density of intra-cluster ones.• We provide a regret upper bound for our setting. Our bound highlights the advantage of our algorithm in high dimensional settings, and for large graphs.• We support our theoretical findings by extensive numerical experiments on simulated data that prove the advantage of our algorithm compared to other approaches used for online clustering of bandits.The rest of the paper is organized as follows. Section 2 discusses the relation of our work to the literature. We formulate our problem and state some of our assumptions in Section 3, then we present our bandit algorithm in Section 4. We analyze the problem theoretically in Section 5, and finally, we demonstrate its practical interest via numerical experiments in Section 6. 
related work: 
 Lasso contextual bandits To address the high dimensional setting for linear bandits, several multiarmed bandit papers solve a LASSO [Tibshirani, 1996] problem under different assumptions [Bastani and Bayati, 2019 , Kim and Paik, 2019 , Oh et al., 2021 , Ariu et al., 2022] . They all rely on a previously established compatibility or RE condition [Bühlmann and van de Geer, 2011] , that they adapt to the non-i.i.d case. Such assumptions were also used in the multi-task setting by Cella and Pontil [2021] with a Group Lasso regularization [Yuan and Lin, 2006] , and to impose a low rank structure on the task preference vectors in Cella et al. [2023] . In our case, we provide a novel oracle inequality, rather than just generalize an existing one to the non-i.i.d setting, with a newly introduced RE assumption.Clustering of bandits Sequentially clustering bandit tasks was introduced in Gentile et al. [2014] with CLUB algorithm. In CLUB, starting with a fully connected graph, an iterative graph learning process is performed, where edges between users are deleted if their preference vectors are significantly different. As a result, any connected component is seen as a cluster and only one recommendation per cluster is developed. In another work, Li et al. [2019] generalize the setting of Gentile et al. [2014] and address its limitations via including merging operations in addition to splitting. In contrast to these approaches, the algorithm in Nguyen and Lauw [2014] groups users via K-means clustering, and the algorithm in Cheng et al. [2023] relies on hedonic games for online clustering of bandits.Furthermore, Yang and Toni [2018] make use of community detection techniques on graphs to find user clusters. Gentile et al. [2017] study the clustering of the contextual bandit problem where their proposed algorithm, named CAB, adaptively matches user preferences in the face of constantly evolving items. Our work fundamentally differs from the previous ones on two aspects. First, we assume access to a graph encoding relations between users, which is more informative than a complete graph. Second, we do not keep track of a model for each cluster, but rather we integrate a prior over the graph via a graph total variation regularizer that enforces a piecewise constant behaviour for the estimated preference vectors.Multi-task learning Several contributions assume some underlying structure that links the bandit tasks. In Cella and Pontil [2021] , task preference vectors are assumed to be sparse and to share their sparsity support, implying that they lie in a low-dimensional subspace with dimensions aligning with the canonical basis vectors. This idea is further generalized in Cella et al. [2023] , where the tasks are assumed to be confined to an arbitrary unknown low-dimensional subspace. That work improves upon Hu et al. [2021] by not requiring the knowledge of the small dimenson of the task space. The underlying structure linking tasks can also be a graph encoding relations between them [Cesa-Bianchi et al., 2013, Yang and Toni, 2018] , which is our case. However, while they assume smoothness as a prior, we assume piecewise constant behavior. 
problem setting: 
 We consider a linear bandit setting, with a finite number of tasks representing users in a recommendation system for example. For each task the agent has to choose among K arms, each associated to a d-dimensional context vector. All interactions over a horizon of T time steps. We further assume that we have access to an undirected graph G = (V, E), with vertex set V representing the tasks and edge set E encoding the relationships between them. We identify the vertex set V with the set of vertex indices [|V|] . Thus, we consider E to be a subset of V 2 , where every edge (m, n) ∈ E has weight w mn > 0, with m < n. The tasks' preference vectors are denoted by {θ m } m∈V ⊂ R d verifying ∥θ m ∥ ≤ 1 ∀m ∈ V, which we concatenate as row vectors into matrix Θ ∈ R |V|×d . The latter represents a graph vector signal, assumed to be piecewise constant over G.At a round t ∈ N ⋆ , a user m(t) ∈ V is selected uniformly at random and served an arm with context vector x(t) from a finite action set A(t) ⊂ R d with size K, depending on their estimated preference vector θm(t) (t) ∈ R d . We assume the expected reward to be linear, with an additive, σ-sub-Gaussian noise conditionally on the past. Formally, denoting by F 0 the trivial sigma-algebra, and for all t ≥ 1, by F t the sigma-algebra generated by history set {m(1), x(1), y(1), • • • , m(t), x(t), y(t), m(t + 1)}, the received reward y(t) is given by yEQUATIONAt the end of a round t, all preference vectors are updated into a new estimation Θ(t) while leveraging the structure of graph G, formally by solving the following optimization problem:EQUATIONwhere ∥•∥ denotes the Euclidean norm for vectors. The performance of our policy is assessed by the expected regret over the T interaction rounds for all tasks:EQUATIONwherex ⋆ (t) ∈ arg max x∈A(t) θ m(t) , x .The Optimization problem in ( 2) is an instance of the Network Lasso [Hallac et al., 2015] . Other instances of the same type were studied by Jung et al. [2018] , Jung and Vesselinova [2019] , Jung [2020] . The objective is characterized by its second term that, while being just the Laplacian regularization without squaring the norms, promotes a piecewise constant behavior rather than smoothness. For real-valued signals (d = 1), this regularization has been extensively studied for image and graph signal denoising, for the problem of trend filtering on graphs [Wang et al., 2016] .According to Wang et al. [2016] , that regularization better adapts to the heterogeneity of smoothness of the signal and induces a cluster structure in the data: similar users will not only have similar models but the same model, which offers a compression of the overall model over the graph. Note that our setting is cluster agnostic; our algorithm does not aim to learn the cluster structure explicitly but to exploit it implicitly using the total variation semi-norm as regularization. The latter's strength is controlled via a time-dependent regularization coefficient α(t), which we will express later in the analysis.We formalize our assumption on the context generation as follows.Assumption 1 (i.i.d action sets). Context sets {A(t)} T t=1 are generated i.i.d. from a distribution p over R K×d , such that ∥x∥ ≤ 1∀ x ∈ A(t) ∀t ≥ 1.In addition to the i.i.d assumption, we assume more regularity.Assumption 2 (Relaxed symmetry and balanced covariance). There exists a constant ν ≥ 1 such that for all X ∈ R K×d , p(-X) ≤ νp(X). Furthermore, there exists ω > 0, such that for anypermutation (a 1 , • • • , a K ) of [K], for any i ∈ {2, • • • , K -1}, and for any w ∈ R d , we haveE x ai x ⊤ ai [w ⊤ x a1 < • • • < w ⊤ x a K ] ≼ ωE (x a1 x ⊤ a1 + x a K x ⊤ a K )[w ⊤ x a1 < • • • < w ⊤ x a K ] , where M ≼ N means that N -M is a PSD matrix.This assumption was introduced in Oh et al. [2021] , and has already been used in a multi-task setting by Cella et al. [2023] . Parameter ν controls the skewness, as ν = 1 corresponds to a symmetric distribution. ω decreases with increasing positive correlation between arms. It verifies ω = O(1) for multi-variate Gaussians and uniform distributions over the unit sphere [Oh et al., 2021] . The piecewise constant behaviour of the graph signal Θ is formalized in the next assumption.Assumption 3 (Piecewise constant signal). There exists a partition P of V, such that for any cluster C ∈ P, signal Θ is constant on C, and the graph obtained by taking the vertices in C and the edges linking them is connected.Assumption 3 basically states that the true preference vectors are clustered and that the given graph induces the cluster structure. It is required for our approach to be beneficial, as we will detail in the analysis section. For the sake of clarity, we defer the statement of other technical assumptions to Section 5. 
algorithm: 
 Our policy in Algorithm 1 follows a greedy arm selection rule in a multi-task setting, in the same vein as those presented in Oh et al. [2021] , Cella et al. [2023] . Indeed, as pointed out in Oh et al.[2021], exploration is implicitly incorporated into regularization parameter α(t)'s time dependence.EQUATIONwhere the set of time steps a task m has been selected up to time t is denoted by T m (t). 
analysis: 
 This section provides the main steps of the analysis. One of the paper's contribution lies in finding an oracle inequality of the network lasso problem given a restricted eigenvalue condition holding for the true multi-task Gram matrix. In this regard, the next major challenge and contribution is to show that the empirical multi-task Gram matrix, estimated in the algorithm, satisfies the restricted eigenvalue condition. We start by proving an oracle inequality for the estimation error of Θ, assuming that the condition given by Definition 2 is verified by the empirical data Gram matrix. Then, we prove that the latter assumption actually holds with high probability given that true multi-task Gram matrix satisfies it. Our final contribution in this work is the establishment of a regret bound for our algorithm.We provide additional notations required for the analysis. We denote by ∂P the set of all edges in E connecting vertices from different clusters from partition P (Assumption 3), and we call it the Algorithm 1: Network Lasso Policy Input : T, α 0 > 0, G, function δ Initialization : , where e m is the m th canonical basis vector of R |V| . We defineΘ(0) = 0 ∈ R |V|×d for t ∈ [1, T ] do 1.A V (t) := diag X 1 (t) ⊤ X 1 (t), . . . , X |V| (t) ⊤ X |V| (t) ∈ R d|V|×d|V| ,and subsequently the empirical multi-task Gram matrix up to time step t is given by 1 t A V (t). The following definition introduces quantities related to the clusters defined by partition P, with crucial roles that we will elucidate throughout the analysis.Definition 1 (Cluster content constants). Let C ∈ P be a cluster.• We denote by ∂ v C the inner boundary of C, i.e.the vertices of C that are connected to its complementary. We define the inner isoperimetric ratio of C as ι G (C) := |∂vC| |C| .• By abuse of notation, we denote as B C the incidence matrix restricted to edges linking vertices of C, its associated Laplacian matrix by L C := B ⊤ C B C , and its pseudo-inverse byL † C . The topological centrality index of node m ∈ C w.r.t C is equal to (L † C ) -1 mm . We define the topological centrality index of C by c G (C) := min m∈C (L † C ) -1 mm .The inner isoperimetric ratio of a cluster measures how many "interior" nodes a cluster contains, in the sense that they are not connected to its complementary. It is at most equal to the isoperimetric ratio for weightless graphs as the size of the inner boundary is at most equal to that of the edge boundary, the latter being connected to the algebraic connectivity via the Cheeger inequality [Cheeger, 1970] .The topological centrality index measures the overall connectedness of a vertex in a network and indicates how robust a node is to edge failures [Ranjan and Zhang, 2013] . Also, it can be tied to electricity spreading in a network according to Van Mieghem et al. [2017] . We refer the interested reader to the two previously mentioned works for a detailed account of the properties of the topological centrality index. In the appendix, we show that for binary weights graphs the minimum topological centrality index is at least equal to the algebraic connectivity theoretically and experimentally, where we showcase that the difference between the two can be significant.To proceed, we will need the following definition that introduces several notations to reduce the clutter.Definition 2 (Restricted Eigenvalue (RE) condition and norm). Let {M i } |V| i=1 ⊂ R d×d be a set of positive semi-definite matrices. We say that the matrixM V := diag(M 1 , • • • , M |V| ) verifies the restricted eigenvalue condition with constants κ ≥ 0 and ϕ > 0 if ϕ 2 ∥Z∥ 2 RE ≤ i∈V ∥z i ∥ 2 Mi ∀Z ∈ S with rows {z i } i∈V ,where S is the cone defined by:S := {Z ∈ R |V|×d ; a 1 (G, Θ)∥Z∥ ∂P c ≤ a 2 (G, Θ) Z P F + (1 -κ) + ∥Z∥ ∂P }, a 1 (G, Θ) := 1 - 1 α0 + 2κw(∂P) min C∈P c G (C) , a 2 (G, Θ) := 1 α 0 + √ 2κw(∂P) max C∈P ι G (C),and the RE semi-norm is defined by∥Z∥ RE := Z P F ∨ (1 -κ) + B † ∂P B ∂P Z .To interpret the previous definition, we point out that the sum on the right-hand side of Definition 2 can be written as vec(Z ⊤ ) M V , where vec denotes the operation of stacking a matrix's columns vertically. As a result, the condition is analogous to requiring that M V is invertible with minimum eigenvalue ϕ 2 , but weaker since it holds only for signals Z ∈ S and for the ∥•∥ RE norm. This requirement has the same form as the compatibility assumption for the Lasso [Bühlmann and van de Geer, 2011, Oh et al., 2021] or the restricted strong convexity assumption [Cella et al., 2023] .We further make the following assumption on the true multi-task Gram matrix:Assumption 4 (RE condition for the true multi-task Gram matrix).For k ∈ [K], let Σ k := E x k x ⊤ kbe the Gram matrix of the k th context vector's marginal distribution, let Σ V be the true multi-task Gram matrix of the context vector generating distribution, given byEQUATIONWe assume that Σ V verifies RE condition (Definition 2) with some problem dependent constantsκ ∈ 0, 1 2w(∂P) min C∈P c G (C) and ϕ > 0.This assumption is common to make for Lasso-like bandit problems [Oh et al., 2021 , Ariu et al., 2022 , Cella et al., 2023] . We will later show that it can be transferred to empirical multi-task Gram matrix.This section is dedicated to provide a bound on the estimation error of the Network Lasso problem given in Equation (2) at a particular step t of Algorithm 1.We assume fixed design, meaning that the context vectors are given and fixed, and we are not concerned by their randomness (due to the context generating distribution), nor by the randomness of their number for each user (due to random selection at each time step).For a time step t, we deliver the oracle inequality controlling the deviation between the estimated preference vectors Θ(t) and the true ones Θ. For the sake of simplicity, we provisionally assume that the RE condition holds for the empirical multi-task Gram matrix A V (t).Theorem 1 (Oracle inequality). Assume that the RE assumption holds for the empirical multitask Gram matrix with constants κ ∈ 0, 1 2w(∂P) min C∈P c G (C) and ϕ > 0. Suppose that max m∈V |T m (t)| ≤ bt for some b > 0. Then, with a probability at least 1 -δ(t), we haveΘ -Θ(t) F ≤ 2 σ ϕ 2 √ t f (G, Θ) 1 + 2b |V| log 1 δ(t) + 2b log 1 δ(t) ,wheref (G, Θ) := α 0 a 2 (G, Θ) + √ 21 ≤1 (κ)w(∂P)   a 2 (G, Θ) + √ 21 ≤1 (κ)w(∂P) a 1 (G, Θ) min C∈P c G (C) + 1   .The proof of the previous theorem mainly relies on a decomposition of the estimation error signal into two parts: one is the projection of the error onto its mean per cluster value, that is, every node within the same cluster is mapped to the mean estimation error of its cluster. The second part of the decomposition is simply the residual part i.e. the deviation from the mean per cluster value, which is related to the incidence matrices of each cluster. The probabilistic statement comes from a high probability bound on the Euclidean norm of an empirical vector process associated with our problem, using a generalization of the Hanson-Wright inequality to the subgaussian case [Hsu et al., 2012, Theorem 2.1] . Compared to the bound of Jung [2020, Theorem 1], we bound a norm of the estimation error rather than just the total variation semi-norm. Additionally, the bound exhibits different behavior depending on whether κ > 1. Indeed, due to the expressions of a 1 (Θ, G) and a 2 (Θ, G), in the case where κ > 1, the bound significantly decreases with the products w(∂P) min C∈P ι(C) andw(∂P) max C∈P c G (C) -1 2, which are both small enough for dense intra-cluster edge links and sparse inter-cluster ones. However, when κ < 1, the w(∂P) term might dominate if it is moderately large, and its effect can only be mitigated via a small subgaussianity constant σ or a large enough RE condition constant ϕ.To establish the oracle inequality, we assumed that the RE condition holds for the empirical multi-task Gram matrix. The goal of this section is to prove this holds with high probability. To this end, we use the same strategy as in Oh et al. [2021] , Cella et al. [2023] . We prove that on the one hand, given the empirical multi-task Gram matrix inherits the RE condition from its adapted counterpart since it concentrates around it. On the other hand, we prove that the adapted Gram matrix verifies the RE condition due to Assumption 1, 2 and 4 made on the context generation distribution.Theorem 2 (RE condition holding for the empirical multi-task Gram matrix). Under assumptions 2 and 4, let t ≥ 1, and let κ, ϕ be the constants from Assumption 4. Assume that max m∈V |T m (t)| ≤ bt.Then, for anyγ ∈ 0, 1 + a2(G,Θ)+(1-κ) + √ 2w(∂P) a1(G,Θ) -2, the empirical multi-task Gram matrix verifies the RE condition with constants κ and φ, withEQUATION)with a probability at least equal to 1 -6d|V| exp-3γ 2 φ4 (min C∈P (c G (C) ∧ cG (C) 2 )t 6b + 2 √ 2γ φ2, whereφ := ϕ √ 2νω and cG (C) := c G (C) ∧ |C| ∀C ∈ P.The proof follows the same approach as in Oh et al. [2021] , Cella et al. [2023] ; we prove that the RE condition transfers from the true multi-task Gram matrix to its adapted counterpart V V (t), defined as follows:EQUATIONwhereEQUATIONThis transfer relies on the work of Oh et al. [2021, lemma 10] . The other step of the proof is showing that the empirical multi-task Gram matrix and V V (t) become close to each other with high probability after sufficiently many time steps, the respective distance between the two is measured with a matrix norm induced by the RE semi-norm and the restriction to set S (Definition 2). The bound showcases a dependence on min C∈P c G (C) ∧ |C|, which is of the same order as |C| for a fully connected cluster with vertices C. It is also clear that with a higher minimum centrality of a cluster, the probability of satisfying the RE condition increases.To bound the regret, we bound the expected instantaneous regret for each round t ≥ 1. This bound relies on the oracle inequality holding and on the RE condition being satisfied for the empirical Gram matrix, both with high probability. These two conditions are ensured and Theorem 1 and Theorem 2.Theorem 3 (Regret bound). Let the mean horizon per node be T= T |V| . Let min C∈P c G (C)going asymptotically to infinity and max C∈P ι G (C) going asymptotically to zero as well asmax C∈P ι G (C)w(∂P) and w(∂P) min C∈P c G (C)going asymptotically to zero. Under assumptions1 to 4 and κ < 1, the expected regret of the Network Lasso Bandit algorithm is upper bounded as follows:R(|V|T ) = O   T min C∈P c G (C) |V| + log T |V| + 4 V log T |V| + 1 A log(d|V|)   , with A = 3γ 2 min C∈P (c G (C) ∧ c2 G (C)) 6 log(|V|) √ |V| + 2 √ 2γ.Our regret is mainly formed of two parts. The first one is the sublinear time-dependent term and represents the bulk of horizon dependence. Interestingly, it does not depend on the dimension, which is a consequence of using the concentration inequality from Hsu et al. [2012] . Interestingly, it decreases as the topological centrality index grows with the graph size, which proves the importance of intra-cluster high connectivity.The second significant term comes from ensuring the RE condition for the empirical multi-task Gram matrix, and can be interpreted as the number of time steps necessary for it to hold, as pointed out by Oh et al. [2021] . It has a logarithmic dependence in the graph size and in the dimension, which is a characteristic of regret bound of the "lasso type". Also noteworthy is that the regret grows with log(d) only in the time-independent term, making our policy useful in high-dimensional settings. 
experiments: 
 We provide experiments to showcase the effect on the problem's parameters on our algorithm's performance as well as highlighting its advantageous performance compared to other algorithms. At each time step, the algorithm solves the network lasso problem (2) via a primal-dual algorithm used in Jung [2020] .We compare our algorithm to several baselines of the literature. On the one hand, baselines relying on a given graph, GOBLin [Cesa-Bianchi et al., 2013] and GraphUCB [Yang et al., 2020] that use the Laplacian to smooth the preference vectors. On the other hand, we consider online clustering of bandits baselines, namely CLUB [Gentile et al., 2014] and SCLUB [Li et al., 2019] . Since these latter approaches start with a fully connected graph, we provide them the known graph for a fair comparison. As a sanity check, we also compare the independent task learning case with LinUCB (LinUcbITL) where each task is solved independently, and to the case of a LinUCB agent for each cluster (LinUcbOracle). The graph used is generated using stochastic block models in order to ensure that the generated graph induces a cluster structure, where an edge is constructed with probability p within clusters and q between clusters.Experimentally, we found that normalizing the adjacency matrix, that is we utilize the following normalized edges:w mn = 1 deg(m) deg(n), where deg(m) denotes the degree of node m, yields significantly better results. Indeed, such a normalization makes the algorithm focus more on edges between low-degree nodes, which improves the propagation of the collected information within the graph. In all experiments we have set α 0 = 0.1.Our results clearly showcase an improvement compared to the other baselines. Apart from the oracle that has complete knowledge of all clusters from the beginning, our policy performs significantly better than the rest beyond the error margins, covering one standard deviation at ten repetitions. We provide results for up to |V| = 500 nodes showing the effective transfer of knowledge within the graph.Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [Yes] Justification: While training and testing sets are not part of our paper as it is about bandit algorithms, we provide the source of the optimization algorithm we use to solve Equation (2).Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.• The full details can be provided either with the code, in appendix, or as supplemental material. 
conclusion and future perspectives: 
 In this work, we proposed a multi-task bandit framework that solves the case where the task preference vectors are piecewise constant over a graph. To this end, we used the Network Lasso policy to estimate the task parameters, which bypasses explicit clustering procedures. We showed a sublinear regret bound and as a byproduct, we proved a novel oracle inequality that relies on the small size of the boundary as well as on the high value of the topological centrality index of each node within its cluster. Our experimental evaluations highlight the advantage of our method, especially when either the number of dimensions or nodes increases.Due to the technical similarity of our problem with the Lasso, a natural extension would be to extend it to a thresholded approach, in the same vein as [Ariu et al., 2022] . Another possible extension would be to use regularization with higher order total variation terms that impose a piecewise polynomial signal on a graph, as explained for scalar signals in Wang et al. [2016] , Ortelli and van de Geer A Some helper resultsProposition 1 (Bounds on norms of matrix products). Let M ∈ R m×n and N ∈ R n×p . Then∥MN∥ q,1 ≤ ∥M∥ ∞,1 ∥N∥ q,1 ∀q ∈ [1, ∞] ∥MN∥ F ≤ ∥M∥∥N∥ F ∥MN∥ F ≤ ∥M ⊤ M∥ ∞,∞ ∥N∥ 2,1 ∥MN∥ 2,1 ≤ ∥M∥ 2,1 ∥N∥ Proof.First inequality For any q ∈ [1, ∞], we have:e ⊤ i MN q = e ⊤ i M n j=1 e j e ⊤ j N q ≤ max 1≤j≤n e ⊤ i Me j n j=1 e ⊤ j N q = max 1≤j≤n |(M) ij |∥N∥ q,1Second inequality We have∥MN∥ 2 F = p j=1 ∥MNe j ∥ 2 ≤ p j=1 ∥M∥∥Ne j ∥ 2 = ∥M∥∥N∥ 2 F Third inequality We have ∥MN∥ 2 F = Tr(MNN ⊤ M ⊤ ) ≤ M ⊤ M ∞,∞ NN ⊤ 1,1Elements of (i, j) entry of matrix NN ⊤ is the inner product e ⊤ i N, e ⊤ j N . Hence, we haveNN ⊤ 1,1 = i,j e ⊤ i N, e ⊤ j N ≤ i,j e ⊤ i N e ⊤ j N = ∥N∥ 2 2,1 .Fourth inequality We have∥MN∥ 2,1 = m i=1 ∥e i MN∥ ≤ m i=1 ∥e i M∥∥N∥ = ∥M∥ 2,1 ∥N∥Proposition 2 (Decomposition of a signal over a graph). For any C ∈ P EQUATION)whereJ C = 1 C 1 ⊤ C |C| , Q C = B † C B C ∀C ∈ P and Q ∂P c := B † ∂P c B ∂P c .While C∈P J C projects each entry of a graph signal onto the mean vector value of its respective cluster, its residual Q ∂P c can be interpreted as the projection onto the respective entries deviation from its cluster mean value.Proof. Since the proof of the first point is trivial, we directly treat the second point. Denoting B † |C the pseudo-inverse of B |C it is a well-known linear algebra result that the matrixQ |C := B † |C B |C is the projector onto the null space of B |C . Since C is connected, the null space of B |C is unidimensional,and is generated by vector 1 |C| ∈ R |C| having only ones as coordinates. Since the projector into that nullspace isJ |C| := 1 |C| 1 |C| |C| , we deduce that Z |C = J |C| Z |C + Q |C Z |C =⇒ Z C = J C Z C + Q C Z C = J C Z + Q C Zwhere in the last line,Q C := B † C B C . Consequently, we have Z = C∈P Z C = C∈P J C Z + Q C ZTo prove the second point, we recall that B ∂P c is the incidence matrix obtained by setting rows Also let a(G) be its algebraic connectivity, defined as the minimum non null eigenvalue of L. Then• c(G) = ∥L∥ -1 ∞,∞ . • c(G) ≥ a(G). • If G is weightless, then c(G) ≤ N 2 N -1 . Proof. Since L is PSD, L † is PSD and hence L † ∞,∞ is equal to the maximum diagonal entry of L † .Taking the inverse proves the first point. Also, this implies thatEQUATIONwhere we used the fact that ∥•∥ ∞,∞ ≤ ∥•∥ for matrices. This proves the second point of the proposition.For the last point, assume G is weightless, let L comp be the Laplaciane of complete graph built on the vertices of G. Then we have L comp = N (I N -J N ), where J is the square matrix of dimension N having 1/N as entries. From Fontan and Altafini [2021, Lemma 4], we haveL † comp = (L comp + N J N ) -1 - 1 N J N = I N N - 1 N J N (13) which has diagonal elements 1 N -1 N 2 .On the other hand, L ≼ L comp Hence, by Fontan and Altafini [2021, lemma 4] we have for anyu ̸ = 0 L † = (L + aJ N ) -1 -J N /a ≽ (L comp + aJ N ) -1 -J N /a = L † compThis implies that the maximum diagonal entry of L † is at least equal to that ofL † comp , i.e.to 1 N -1 N 2 .Taking the inverse of that entry finishes the proof.Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [Yes] Justification: Error bars are provided in the plots.Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.• The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).• The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)• The assumptions made should be given (e.g., Normally distributed errors).• It should be clear whether the error bar is the standard deviation or the standard error of the mean.• It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified.• For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).• Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.• The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.• The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?Answer: [Yes] Justification: Our results are theoretical, and their potential harm largely depends on their application.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.• The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [Yes] Justification: It is provided in Appendix D.5 in the appendix.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.• Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.• The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.• If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: Only simulated data are used.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.• Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.• We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [Yes] Justification: All relevant work is properly cited and code is provided to reproduce the results.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL.• The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. 
 
 Appendix: The regularization term can be written more compactly using the incidence matrix of the graph B ∈ R |E|×|V| corresponding to an arbitrary orientation under the following formEQUATION)where the ∥•∥ 2,1 norm denotes the sum of the L 2 norms o the rows of a matrix. 1 We provide notations that we use in the proofs of the different statements, in order to reduce the clutter. We define E := Θ -Θ as the error signal, and its rows by {ϵ m } |V| m=1 .While C k=1 J C projects each entry of a graph signal onto the mean vector value of its respective cluster, its residual Q ∂P c can be interpreted as the projection onto the respective entries deviation from its cluster mean value.Let η m be a vector, vertically concatenated by noise terms of rewards received by node m, then we define K ∈ R |V|×d as the matrix of vertically concatenated row vectors η ⊤ m X m .In this section, we present all intermediary theoretical results leading to Theorem 1 stating the oracle inequality. To reduce the clutter, we omit the dependence on t of several quantities. For instance, we write α and Θ instead of α(t) and Θ(t).Lemma 1 (A first deterministic inequality). Let t be a time step. We have Semi-norm associated defined by PSD matrix A:1 2tα m∈V ∥X m ϵ m ∥ 2 + ∥E∥ ∂P c ≤ 1 tα ⟨K, E⟩ + ∥E∥ ∂P (15)∥x∥ 2 A := x ⊤ Ax ∥•∥ F matrix Frobenius norm ∥•∥ p,qq-norm of the vector with coordinates equal to the p-norm of rows ∥•∥ I , I ⊆ E Total variation norm of signal over edges of I A † Moore-Penrose pseudo-inverse of matrix A vec vectorization operator consisting in concatenating the columns vertically ⊗ Kronecker product1 C ∈ R |V|Vector having elements equal to 1 at coordinates corresponding to vertices in C and 0 elsewhere J C ∈ R |V|×|V| equal to 1 C 1 ⊤ C |C| Q C ∈ R |V|×|V| equal to B † C B C Q I ∈ R |V|×|V| , I ⊆ E equal to B † I B I e k elementary vectorsm ∈ R d×d X ⊤ m X m (potentially associated to time t) A V ∈ R d|V|×d|V| diag(A 1 , • • • , A m ) K ∈ R |V|×d matrix of vertically concatenated row vectors η ⊤ m X m Table 1: Notation table.Proof. By optimality of Θ, we haveEQUATION)where the second line holds by definition of the observed rewards.On the one hand, given a user index m ∈ V, and since by definition of the observed rewards we have we have for the least squared termsX m θm -y m 2 = X m θm -X m θ m -η m 2 = ∥X m ϵ m -η m ∥ 2 = ∥X m ϵ m ∥ 2 + ∥X m θ m -y m ∥ 2 -η ⊤ m X m ϵ mwhere we used the fact that y m = X m θ m + η m , which holds by definition of the observed rewards.Summing over the users, and using the definition of K, we haveEQUATIONOn the other hand, we have for the estimated preference vectors∥Θ∥ E = (m,n)∈E w mn θm -θn = (m,n)∈∂P w mn θm -θn + (m,n)∈∂P c w mn θm -θn = Θ ∂P + Θ ∂P c, For the true ones, and for any C ∈ P, let E C denote the edges linking the nodes of set of nodes C. It isclear that ∂P c = C∈P E C as a disjoint union, hence ∥Θ∥ E = (m,n)∈E w mn ∥θ m -θ n ∥ = (m,n)∈∂P w mn ∥θ m -θ n ∥ + (m,n)∈∂P c w mn ∥θ m -θ n ∥ = ∥Θ∥ ∂P + C∈P (m,n)∈E C w mn ∥θ m -θ n ∥ = ∥Θ∥ ∂Pwhere the last equality holds due to the cluster assumption.Hence, we haveEQUATIONwhere the first inequality holds due to the triangle inequality, and the last one since ∥Θ∥ ∂P c = 0.Combining Equations ( 16) to (18), we obtain the result of the statement.In the proof for the oracle inequality, we utilize projection operators on the graph signal, that we define as followed:While C k=1 J C projects each entry of a graph signal onto the mean vector value of its respective cluster, its residual Q ∂P c can be interpreted as the projection onto the respective entries deviation from its cluster mean value.Lemma 2 (Bounding the error restricted to the boundary). The total variation of E restricted to the boundary verifiesEQUATIONProof. The proof relies on a decomposition of the ∥E∥ ∂P term from Proposition 2. We haveEQUATION)where E P is obtained by setting the error signal on every cluster to its mean.For the first term on the right-hand side, let us denote by ϵ C the value of any row of E P belonging to cluster C, which is equal to the mean of errors E over that cluster. Also, we denote by (E P ) ∂P the signal obtained from E P by setting its rows corresponding to nodes that are not adjacent to any edge in the boundary ∂P to zeros. Also, let ∂ v C denote the inner boundary of set of nodes C,i.e. nodes of C that connect it to its complementary. Then it holds that:EQUATIONFor the second term, we haveEQUATION)The result is obtained by combining Equations ( 20) to ( 22).Theorem 4 (Theorem 2.1 of Hsu et al. [2012] ). At time step t, let A ∈ R b×t where b ∈ N * , and let v ∈ R t be a random vector such that for some σ ≥ 0, we haveE [exp(⟨u, v⟩)] ≤ exp ∥u∥ 2 σ 2 2 ∀u ∈ R t .Then for any δ ∈ (0, 1), we have with a probability at least 1 -δ:∥Av∥ 2 ≤ σ 2 ∥A∥ 2 F + 2 A ⊤ A F log 1 δ + 2∥A∥ 2 log 1 δ .Lemma 3 (Empirical process bound). Let X m ∈ R |Tm|×d denotes the matrix of collected context vectors for task m ∈ V, then, given collected context matrices {X m } m∈V , for any δ ∈ (0, 1) we have with probability of at least 1 -δ:∥K∥ F ≤ α δ (t) α 0 t,whereEQUATIONProof. We recall that K ∈ R t×d is the matrix obtained by stacking the row vectors η ⊤ m X m vertically.On the one hand, we haveEQUATIONwhereX V := diag(X 1 , • • • , X |V| ) ∈ R t×d|V| .On the other one, for any u = (u 1 , • EQUATION)From Equations ( 24) and ( 25), we can apply Theorem 4 to matrix X V and random vector η, which implies that with a probability at least 1 -δ, we have∥X V η∥ ≤ σ Tr m∈V A m + 2 m∈V ∥A m ∥ 2 F log 1 δ + 2 max m∈V ∥A m ∥ log 1 δ ,where we used the equalities∥X V ∥ F = m∈V Tr(A m ), ∥X V ∥ 2 = max m∈V ∥A m ∥ and X V X ⊤ V 2 F = X ⊤ V X V 2 F = m∈V ∥A m ∥ 2 F .To arrive the the statement of the theorem, we use the fact that the context vectors have Euclidean norms of at most 1.Proposition 4 (Probabilistic inequality). With a probabability at least 1 -δ, we haveEQUATION)EQUATIONProof. The proof is a combination of the results of Lemmas 1 to 3. We have1 2tα δ m∈V ∥X m ϵ m ∥ 2 + ∥E∥ ∂P c ≤ 1 tα δ ⟨K, E⟩ + ∥E∥ ∂P (by Lemma 1) ≤ 1 α 0 ∥E∥ F + κ∥E∥ ∂P + (1 -κ)∥E∥ ∂P (by Lemma 3) ≤ E P F α 0 + ∥E∥ ∂P c α 0 min C∈P c G (C) + κw(∂P)   √ 2 max C∈P ι G (C) E P F + 2 ∥E∥ ∂P c min C∈P c G (C)   + (1 -κ)∥E∥ ∂P ,where the last line is an application of Lemma 2. Grouping the terms by the type of norm applied to E finishes the proof.Theorem 1 (Oracle inequality). Assume that the RE assumption holds for the empirical multitask Gram matrix with constants κ ∈ 0, 1 2w(∂P) min C∈P c G (C) and ϕ > 0. Suppose that max m∈V |T m (t)| ≤ bt for some b > 0. Then, with a probability at least 1 -δ(t), we haveΘ -Θ(t) F ≤ 2 σ ϕ 2 √ t f (G, Θ) 1 + 2b |V| log 1 δ(t) + 2b log 1 δ(t),wheref (G, Θ) := α 0 a 2 (G, Θ) + √ 21 ≤1 (κ)w(∂P)   a 2 (G, Θ) + √ 21 ≤1 (κ)w(∂P) a 1 (G, Θ) min C∈P c G (C) + 1   .Proof. Using the previously established results, we obtain1 2t m∈V ∥X m ϵ m ∥ 2 + α∥E∥ ∂P c ≤α δ a 2 (Θ, G)∥E P ∥ F + α δ (1 -κ) + ∥E∥ ∂P (by Proposition 4) =α δ a 2 (Θ, G)∥E P ∥ F + α δ (1 -κ) + B ∂P B † ∂P B ∂P E 2,1(by properties of the pseudo-inverse)≤α δ a 2 (Θ, G)∥E P ∥ F + α δ ∥B ∂P ∥ 2,1 1 ≤1 (κ)(1 -κ) + B † ∂P B ∂P E (by Proposition 1) ≤α δ (a 2 (Θ, G) + 1 ≤1 (κ) √ 2w(∂P))∥E∥ RE (by definition of the ∥∥ RE norm) ≤α a 2 (Θ, G) + 1 ≤1 (κ) √ 2w(∂P) ϕ √ t m∈V ∥ϵ m ∥ 2 Am(using the RE assumption)EQUATION)where the last inequality holds for any β > 0, and is a consequence of the property that uv ≤u 2 + v 2 2 for any u, v ∈ R.As a result, we can bound the norm of Q ∂P c E as follows: 29) with β = 1).∥Q ∂P c E∥ F = B † ∂P c B ∂P c E F ≤ L † ∂P c ∞,∞ ∥E∥ ∂P c ≤ 2α δ (a 2 (Θ, G) + 1 ≤1 (κ)∥B ∂P ∥ 2,1 ) 2 ϕ 2 a 1 (Θ, G) min C∈P c G (C) (Equation (We can also bound the norm of E P as follows:EQUATION)The result is then obtained by combining Equations ( 30) and ( 31) along with using the fact thatE = E P + Q ∂P cE and the expressions of a 1 (Θ, G) and a 2 (Θ, G), and bounding α δ (t) as follows:α δ (t) 2 α 2 0 = σ 2 t 2   m∈V ∥X m ∥ 2 F + 2 m∈V ∥X m X ⊤ m ∥ 2 F log 1 δ + 2 max m∈V ∥X m ∥ 2 log 1 δ   ≤ σ 2 t 2   t + 2 m∈V |T m (t)| 2 log 1 δ + 2 max m∈V |T m (t)| log 1 δ   ≤ σ 2 t 2 t + 2t log 1 δ + 2t log 1 δ ≤ 2 σ 2 t 1 + log 1 δ 2 B.3 Inheriting the RE condition from the true to the empirical data Gram matrix B.3.1 From the adapted to the empirical multi-task Gram matrix Lemma 4 (Bounding a quadratic form using projections). Let M 1 , • • • , M p ∈ R d×d be symmetric matrices, and let J := 1 p 11 ⊤ , and Q = I -J. Then, for any Z ∈ R p×d with rows {z i } p i=1 , we have:EQUATION)where we used the fact that zi -z = Z ⊤ e i -Z ⊤ Je i = Z ⊤ Qe i .Let us now examine every term on the right-hand side of Equation ( 32). For the first term, we haveEQUATIONFor the second term, we haveEQUATIONFinally, for the last term, we haveEQUATIONCombining Equations ( 33) to (35) yields the result.We also define an operator norm that is induced by the ∥∥ RE introduced in Definition 2.Definition 3 ((RE,S)-induced operator norm). Let {M m } m∈V ⊆ R d×d be symmetric matrices associated to the graph nodes V, and letM V := diag M 1 , • • • , M |V| ∈ R d|V|×d|V| .For any cluster C ∈ P, let the cluster mean and mean of squares associated to those matrices be given byM C := 1 |C| m∈C M m , M 2 C := 1 |C| m∈C M 2 m .The RE-induced operator norm of M V is defined asEQUATIONWe first start by establishing that given the closeness of two PSD matrices in a certain sense, the RE condition can be transferred between them.Proposition 5(Restricted spectral norm). Let Z ∈ R |V|×d verifying a 1 (G, Θ)∥Z∥ ∂P c ≤ a 2 (G, Θ) Z P F + (1 -κ) + ∥Z∥ ∂PLet {M m } m∈V ⊆ R d×d be symmetric matrices associated to the graph nodes V, and letM V := diag(M 1 , • • • , M |V| ) ∈ R d|V|×d|V| .Then we have:EQUATION)Proof. For any cluster C, we denote by B C the incidence matrix obtained by setting the rows of B outside the edges linking nodes in C to null vectors. The latter's nullspace is the span of the vector 1 Chaving coordinates 1 at nodes in C and zeros elsewhere. Hence, the projector onto the orthogonal of1 C is Q C := B † C B C .On the one hand, for any signal Z ∈ R |V|×d we have∥Z∥ ∂P c = C∈P ∥B C Z∥ 2,1 ≥ C∈P B † C B C Z F L † C ∞,∞ ≥ min C∈P c G (C) C∈P ∥Z∥ Q CHence, by the proposition's assumptions, Z verifiesEQUATION)where we used Equation ( 9).This allows us to bound every term in Equation ( 38). For the second term on the right-hand side, we haveC∈P M 2 C ∥Z∥ Q C ∥Z∥ J C ≤ max C∈P M 2 C Z P F C∈P ∥Z∥ 2 Q C ≤ min C∈P c G (C) -1 2 a 1 (G, Θ) max C∈P M 2 C (a 2 (G, Θ) + (1 -κ) + ∥B∥ 2,1 )∥Z∥ 2 RE (39)As for the third term, we haveC∈P max m∈C ∥M m ∥∥Z∥ 2 Q C ≤ max m∈V ∥M m ∥ C∈P ∥Z∥ Q C 2 ≤ max m∈V ∥M m ∥ min C∈P c G (C) -1 a 1 (G, Θ) 2 (a 2 (G, Θ) + (1 -κ) + ∥B∥ 2,1 ) 2 ∥Z∥ 2 RE (40) Consequently, denoting v = a 2 (G, Θ) + (1 -κ) + ∥B∥ 2,1 a 1 (G, Θ), and combining Equations ( 38) to ( 40), we obtainm∈V z ⊤ m M m z m max C∈P M C + 2v max C∈P M 2 C + v 2 max i∈V ∥M i ∥ ∥Z∥ 2 RE ≤ max C∈P M C ) ∨ min C∈P c G (C) -1 max C∈P M 2 C ∨ min C∈P c G (C) -1 max i∈V ∥M i ∥ (1 + v) 2 ∥Z∥ 2 RE ,which finishes the proof.Proposition 6 (Inheritance of a RE condition from a close matrix). Assume that the matrix V V verifies the RE condition with constant ϕ > 0, and thatA V t -V V op,RE≤ γϕ 2 for someγ ∈ 0, 1 + a2(G,Θ)+(1-κ) + √ 2w(∂P) a1(G,Θ) -2 . Then A V t verifies the RE condition with constant φ = ϕ 1 -γ 1 + a 2 (G, Θ) + (1 -κ) + √ 2w(∂P) a 1 (G, Θ) 2 (41)Proof. From Proposition 4, we know that1 t ϵ ⊤ V A V ϵ V = 1 |V| ϵ ⊤ V V V ϵ V + ϵ ⊤ V ∆ V ϵ V ≥ 1 |V| ϵ ⊤ V V V ϵ V -ϵ ⊤ V ∆ V ϵ V ≥   ϕ 2 -max m∈V ∥∆ V ∥ op,RE 1 + a 2 (G, Θ) + (1 -κ) + ∥B ∂P ∥ 2,1 a 1 (G, Θ) 2   ∥E∥ 2 RE ≥   ϕ 2 -γϕ 2 1 + a 2 (G, Θ) + (1 -κ) + ∥B ∂P ∥ 2,1 a 1 (G, Θ) 2   ∥E∥ 2 REwhere the third inequality is an applicaiton of Proposition 5.Theorem 5 (Matrix Freedman Inequality, Tropp [2011] ). Consider a matrix martingale {M(t)} t≥1 with dimension d 1 × d 2 . Let {N(t)} t≥1 be the associated difference sequence. Assume that for some A > 0, we have ∥N(t)∥ ≤ A ∀t ≥ 1 almost surely. Define for any t ≥ 1:W col (t) := t τ =1 E N(τ )N(τ ) ⊤ |F τ -1 W row (t) := t τ =1 E N(τ ) ⊤ N(τ )|F τ -1 .Then, for any u, v > 0, P [∃t ≥ 1; ∥M(t)∥ ≥ u and ∥W col ∥(t) ∨ ∥W row (t)∥ ≤ v] ≤ (d 1 + d 2 ) exp - 3u 2 6v + 2Au Corollary 1. Let {N(τ )} t τM(n) = n i=1 N(t i ) -E [N(t i )|F ti-1 ] (42) Then {M(n)} N n=1 is a martingale adapted to the filtration {F tn } N n=1 . Moreover,if ∥N(τ )∥ ≤ b ∀τ ∈ [t]for some b > 0, then we haveEQUATION) Proof. We denote E [•|F s ] as E s [•] for any s ∈ N. Also, let C(s) := E s-1 [N(s)], which is F s-1 -measurable by construction. We have for any n ∈ [N ], E tn-1 [C(t n )] = E tn-1 [E tn-1 [N(t n )]] = E tn-1 [N(t n )] (44) =⇒ E tn-1 [N(t n ) -C(t n )] = 0 (45)where the first equality is due to the tower rule since F tn-1 ⊂ F tn-1 . Also, we have for any τ ≥ 1∥N(τ ) -C(τ )∥ 2 = (N(τ ) -C(τ )) 2 (46) ≤ Tr (N(τ ) -C(τ )) 2 (47) = Tr (N(τ ) -C(τ )) 2 (48) = ∥N(τ )∥ 2 F -2 Tr(C(τ )N(τ )) + Tr C(τ ) 2 (49) ≤ ∥N(τ )∥ 2 F + Tr C(τ ) 2 ≤ 2b 2 (50)Hence N(τ ) -C(τ ) is integrable for any τ ≥ 1. This shows that M(n) is a sequence of partial sums of matrix martingale differences, hence it is a matrix martingale.The second part of the corollary statement is a consequence of Theorem 5. The boundedness of the sequence of martingale differences has already been established above. To verify the second requirement of the theorem, let us compute bounds on the norms of W col and W row from Theorem 5.Notice that the two matrices are equal since the difference sequence matrices N(t s ) are symmetric.Hence, for any n ∈ [N ], we haveEQUATION)By Theorem 5, we have for any u > 0EQUATIONwhere the last line holds because we showed that the inequality ∥W col (N )∥ ≤ N b 2 holds almost surely.Proposition 7 (Concentration of the empirical multi-task Gram matrix around the adapted one). Let t ≥ 1, b > 0. Then we have:P A V (t) t -V V op,RE > γ max m∈V |T m (t)| ≤ bt ≤ d(2|P|e -A1t +(|V|+|P|)e -A2t +2|V|e -A3t ),whereA 1 := 3γ 2 min C∈P |C|t 6b + 2 √ 2γ A 2 := 3γ 2 min C∈P c G (C)t 6b + 2 √ 2γ min C∈P c G (C) min C∈P |C| A 3 := 3γ 2 min C∈P c G (C) 2 t 6b + 2 √ 2γ min C∈P c G (C)Proof. For γ > 0, let us define∆ m := A V t -V V and G Gram,γ := 1 t ∥∆ V ∥ RE,S ≤ γ ,where ∆ V is block diagonal matrix formed by {∆ m } m∈V . We also define ∆ C and ∆ 2 C in the same pattern of Definition 3. We can express the complementary of this event as the disjunction of a finite number of events as follows:EQUATIONThe first and third event can be bounded by considering the sequence xx ⊤ (τ ) adapted to the filtration{F τ }, verifying xx ⊤ (τ ) ≤.Bounding the probability of the first event Let C ∈ P be a cluster. By definition, we have|C|∆ C (t) = m∈C τ ∈Tm(t) xx(τ ) -E [xx(τ )|F τ -1 ] = τ ∈ m∈C Tm(t) xx(τ ) -E [xx(τ )|F τ -1 ]We will apply Corollary 1 for the sequence of time indices in C, i.e. m∈V T m (t). Hence |C|∆ C is a martingale sequence, and we haveEQUATIONBounding the probability of the third event Let m ∈ V be a task index. We apply Corollary 1 for the sequence of time steps in T m (t). We have∆ m (t) = τ ∈Tm(t) xx(τ ) -E [xx(τ )|F τ -1 ]is a martingale sequence, henceEQUATION)Bounding the probability of the second event Let C ∈ P be a cluster, and let us denote e m the m th canonical vector of R |C| . We have∆ 2 C (t) = 1 |C| m∈C   τ ∈Tm(t) xx(τ ) -E [xx(τ )|F τ -1 ]   2 = 1 |C| m∈C e ⊤ m ⊗   τ ∈Tm(t) xx(τ ) -E [xx(τ )|F τ -1 ]   2 = 1 |C| τ ∈ m∈C Tm(t) e ⊤ m(τ ) ⊗ (xx(τ ) -E [xx(τ )|F τ -1 ]) 2 = 1 |C| τ ∈ m∈C Tm(t) e ⊤ m(τ ) ⊗ xx(τ ) -E e m(τ ) ⊗ xx(τ )|F τ -1 2 ,where the last equality holds since m(τ ) is measurable w.r.t. F τ -1 . We will apply the Corollary 1 to the set of time steps m∈C T m (t) and the adapted sequence e ⊤ m(τ ) ⊗ xx(τ ) of matrices in R d×d|C| .Hence we haveEQUATIONUnion bound We conclude the result of the statement via a union bound using Equation (61).Proposition 8 (Concentration of the empirical multi-task Gram matrix around the adapted one, simplified).propEmpCovConcentrationSimplified Let t ≥ 1, b > 0. Assume that max m∈V |T m (t)| ≤bt. Then we have:P A V t -V V op,RE > γ ≤ 6d|V| exp -3γ 2 (min C∈P (c G (C) ∧ cG (C) 2 )t 6b + 2 √ 2γ ,where cG (C) := c G (C) ∧ |C| ∀C ∈ P.Proof. The proof will rely on simple calculus inequalities. Hence, let u= min C∈P c G (C), v = min C∈P |C|, f = 3γ 2 , g = 6b, h = 2 √ 2γ, which are all positive. Then, we haveA 1 = f u f + g ≥ (u ∧ v)f f + g ≥ (u ∧ v) (1 ∧ u ∧ v)f f + g(1 ∧ u ∧ v) A 2 = f v f + g v u ≥ (v ∧ u)f f + g v∧u u ≥ (v ∧ u)f f + g ≥ (u ∧ v) (1 ∧ u ∧ v)f f + (1 ∧ u ∧ v)g A 3 = f v 2 f + gv ≥ (v ∧ u) 2 f + (v ∧ u)g ≥ (u ∧ v) (1 ∧ u ∧ v)f f + (1 ∧ u ∧ v)gwhere we used the fact that functions of the form x → x β1x+β2 for positive β 1 , β 2 are increasing onR + .As a final step, we use the inequality(1 ∧ x)f f + (1 ∧ x)g ≥ x ∧ 1 f + g taken for x = u ∧ v,we apply the exp(-• t) function and we use the result of Proposition 7, we deduce the result.For all of the proofs in this subsection, we follow an approach similar to that of Oh et al. [2021] . In particular, we use their Lemma 10.Theorem 6 (Lemma 10 of Oh et al. [2021] ). Under Assumption 2 on the context generating distribution, let t ≥ 1. We have for any θ ∈ R d :EQUATIONProposition 9 (RE condition from the true to the adapted Gram matrix). Under Assumption 2, for any t ≥ 1, the adapted Gram matrix V V (t) verifies the compatibility condition with constants κ and ϕ √ 2νω .Proof. For t ≥ 1, we haveEQUATIONLet m ∈ V. We haveEQUATIONNow, let Z ∈ S, where S is defined with constant κ of Assumption 4. Thenm∈V ∥z∥ Vm(t) ≥ 1 2νω m∈V ∥z m ∥ Σ by Equation (67) ≥ ϕ 2 2νω ∥Z∥ 2 RE(by Assumption 4), which finishes the proof.Theorem 2 (RE condition holding for the empirical multi-task Gram matrix). Under assumptions 2 and 4, let t ≥ 1, and let κ, ϕ be the constants from Assumption 4. Assume that max m∈V |T m (t)| ≤ bt.γ ∈ 0, 1 + a2(G,Θ)+(1-κ) + √ 2w(∂P) a1(G,Θ) -2, the empirical multi-task Gram matrix verifies the RE condition with constants κ and φ, withEQUATIONwith a probability at least equal to 1 -6d|V| exp-3γ 2 φ4 (min C∈P (c G (C) ∧ cG (C) 2 )t 6b + 2 √ 2γ φ2, whereφ := ϕ √ 2νω and cG (C) := c G (C) ∧ |C| ∀C ∈ P.Proof. For the sake of readability, let φ = ϕ √ 2νω the compatibility constant of the adapted Gram matrix, according to Proposition 9. Then:EQUATION≤P A V t satisfies the RE condition with constant κ and φ (by Proposition 6),whereφ = φ 1 -γ 1 + a2(G,Θ)+(1-κ) + √ 2w(∂P) a1(G,Θ) 2 .Lemma 5 (Concentration of the fraction of observations per task). lemma Assume that |V| ≥ 2. Then for δ ∈ (0, 1), we have with a probability at least 1 -δ:EQUATIONProof. We have|T m (t)| := t τ =1 [m(τ ) = m], where ∀t, ∀m ∈ V, P [m(t) = m] = 1 |V| , meaning that the binary variable [m(t) = m] follows a Bernoulli distribution B( 1 V ).Then, the random variableX t := [m(t) = m] -1 |V| has mean 0, variance 1 |V| (1 -1 |V| ), and verifies |X t | ≤ 1 -1 |V| since |V| ≥ 2.As a result, via the Bernstein inequality, we have for any m ∈ V, and for any w ≥ 0,P |T m (t)| t ≥ 1 |V| + w ≤ exp - tw 2 2(1 -1 |V| )( 1 |V| + w 3 ) ≤ exp - tw 2 2( 1 |V| + w 3 )For the right-hand side to hold with a probability at most δ ∈ (0, 1), it is sufficient to havet w 2 2( 1 |V| + w 3 ) ≥ log 1 δ ⇐= w 2 2 ≥ 2 1 |V| log 1 δ t and w 2 2 ≥ 2w log 1 δ 3t ⇐= w = 2 1 |V| log 1 δ t + 4 log 1 δ 3tHence, and via a union bound, we getP |T m (t)| t ≥ 1 |V| + 2 1 |V| log 1 δ + 4 3t log 1 δ ≤ δ =⇒ P   max m∈V |T m (t)| t ≥ 1 |V| + 2 1 |V| log 1 δ t + 4 log 1 δ 3t   ≤ |V|δThe result is obtained by adjusting the value of δ. and κ < 1, the expected regret of the Network Lasso Bandit algorithm is upper bounded as follows:R(|V|T ) = O   T min C∈P c G (C) |V| + log T |V| + 4 V log T |V| + 1 A log(d|V|)   , with A = 3γ 2 min C∈P (c G (C) ∧ c2 G (C)) 6 log(|V|) √ |V| + 2 √ 2γ .Proof. For any time step t, we will define a list of good events under which the Oracle inequality and the RE condition for the empirical multi-task Gram matrix both hold with high probability. Then, we will use those bounds to sum up over time steps until horizon T .We formalize these requirements as three families of time-depending "good" events.• G pro (t) is the event that the mean of the empirical process bounded by α(t) up to a constant c, which is equivalent to saying that it converges:EQUATION• G sel (t) is the event that the number of selections of all tasks is bounded by its expected value up to a small constant ρ(t)EQUATION• G RE (t) is the event that the empirical multi-task Gram matrix 1 t A V (t) satisfies the RE condition.EQUATIONEvent G pro (t) is the most straightforward to cover since our bound on the empirical process given in Lemma 3 holds with a probability of at least 1 -δ(t), thus:EQUATIONwhere we included the time dependency on δ(t) in contrast to the previous section. This way we emphasize to adjust δ(t) after each round, to guarantee a sub linear regret bound. The probability of event G sel (t) can be determined using Bernstein's inequality:From Lemma 5 we can select ρ(t) = 2 t |V| log |V| δ sel (t) + 4 3 log |V| δ sel (t) as well as P [G sel (t) c ] ≤ δ sel (t).Now, given the event probabilities, we condition the instantaneous regret r(t) on the good events at a time t > t 0 . We have for its expectation:EQUATIONwhere we used the worst case bound r(t) ≤ 2 if any one of the good events does not hold.Bounding the regret Inserting our results of the event probabilities, the oracle inequality and the decomposition of the expected instantaneous regret in Equation ( 76) and bounding the sum over rounds, yields the final result. Thus, we start by bounding the sum over the first term i.e. the expected regret in case all good events hold:T t=1 E [r(t)|G pro (t) ∩ G RE (t) ∩ G sel (t)] ≤ T t=1 Θ -Θ(t) FTaking the result of our oracle inequality in Theorem 1, we point out that only α(t) is time dependent such that the rest of the terms can be pulled outside the sum:T t=1 Θ -Θ(t) F ≤ T t=1 2 σ φ2 √ t f (G, Θ) 1 + 2b |V| log 1 δ(t) + 2b log 1 δ(t) = 2σ φ2 f (G, Θ) T t=1 1 t + 2b t 2|V| log(t) + 4b t log(t) ≤ 2σ φ2 f (G, Θ) T 0 1 √ t + 2b t 2|V| log(T ) + 2 log(T ) dt ≤ 2σ φ2 f (G, Θ) 2 √ T + √ 8T |V| + 4 4 32 log(|V|T )T |V| + 16 3 log(|V|T ) log(T ) 4 2|V| log(T ) + 2 log(T ) = O f (G, Θ) √ T φ2 |V| + log T |V| + 4 V log T |V| , where f (G, Θ) := a 2 (G, Θ) + √ 21 ≤1 (κ)w(∂P)   a 2 (G, Θ) + √ 21 ≤1 (κ)w(∂P) a 1 (G, Θ) min C∈P c G (C) + 1   .We upper bounded the sum with an integral i.e. for all t > t 0 :1 |V| + 2 1 t|V| log |V| δ + 4 3t log |V| δ ≤ 1 |V| + 2 2 log |V| |V| |V||V| + 8 log |V| |V| 3 |V| = 1 |V| + 2 |V| 3 |V| log(|V|) + 2 log(|V|) = O log(|V|) |V| = b.Finally we bound the sum over the instantaneous regret term for the bad events:T t=1 2 (P [G pro (t) c |G sel (t)] + P [G RE (t) c |G sel (t)] + P [G sel (t) c ])By construction, we have maxEQUATIONAs for the RE condition event, lettingA := 3γ 2 min C∈P (c G (C) ∧ c2 G (C)) 6b + 2 √ 2γ, we have for any t 0 ≥ 1T t=t0 P [G RE (t) c |G sel (t)] ≤ 6d|V| T t=t0 exp(-At) (by Theorem 2) ≤ 6d|V| e -At0 1 -e -A ≤ 6d|V|e -At0 1 + 1 A ≤ 6d|V|e -At0 1 + 1 Awhere in the last line, we used the inequality exp(A) ≥ A + 1. Hence, for any u > 0, choosingt 0 = |V| ∨ 1 A log 6d|V|(1 + 1 A ) u implies that T t=t0 P [G RE (t) c |G sel (t)] ≤ u.Before we continue with the regret bound, we need to find an appropriate bound on f (G,Θ) φ2 . Given our result in Theorem 1 and assuming that κ > 1, we get:f (G, Θ) φ2 = α 0 a 2 (G, Θ) φ2   a 2 (G, Θ) a 1 (G, Θ) min C∈P c G (C) + 1   = √ 2κw(∂P) max C∈P ι G (C)α 0 + 1   √ 2κw(∂P) max C∈P √ ι G (C)α0+1 α0(min C∈P c G (C) -2κw(∂P)) -1 + 1   1 -γ         1 + √ 2κw(∂P) max C∈P √ ι G (C)α0+1 α     1- 2κw(∂P) min C∈P c G (C)     - 1 min C∈P c G (C)         2 = O   max C∈P ι G (C) + max C∈P ι G (C) + 1 min C∈P c G (C) + max C∈P ι G (C) + 1   = O   1 min C∈P c G (C)   .The first big O notation is obtained due to the fact that for for large min C∈P c G (C) and small max C∈P ι G (C) the denominator term i.e. φ2 behaves like 1 -γ, which leaves the numerator dominating the rest of the term. Now, we simply have to insert all our results into the sum of instantaneous regrets:R(T ) ≤ t 0 + 2u + 8 + O f (G, Θ) √ T φ2 |V| + log T |V| + 4 V log T |V| ≤ |V| + 1 A log 6d|V|(1 + 1 A ) u + 2u + 8 + O f (G, Θ) √ T φ2 |V| + log T |V| + 4 V log T |V| ≤ |V| + 1 A log(12d|V|(1 + A)) + 1 A + 8 + O f (G, Θ) √ T φ2 |V| + log T |V| + 4 V log T |V| ≤ |V| + 1 A log(12d|V|(1 + A)) + 1 A + 8 + O f (G, Θ) √ T φ2 |V| + log T |V| + 4 V log T |V| = O   1 A log(d|V|) + T min C∈P c G (C) |V| + log T |V| + 4 V log T |V|   ,where we set u = 1 2A in the third inequality.Homophily and modularity in social networks Given the large number of users on social networks, one may be able to learn their preferences more quickly by leveraging the similarities between them.This idea relies on the notion of homophily in social networks McPherson et al. [2001] , Easley et al. [2010] . In modelling social networks, users' preferences relationships are encoded in a graph, where neighboring nodes are users with similar preferences. This graph can be known a priori or it can be inferred from previously collected feedback Dong et al. [2019] . Exploiting this information and integrating them into bandit algorithms can lead to a significant increase in performance Yang et al.[2020]. Indeed, the knowledge of user relations allows the algorithm to tackle the data sparsity issue that is inherent to bandit settings.Another fundamental point that can be used for integration of information from social networks is Bandit meta-learning In contrast to the multi-task setting, meta learning deals with sequentially arriving tasks that have to be learnt and generalizing the gained information to improve performance for future tasks. Here, as in the multi-task setting, it is assumed that the tasks share some common structure that is ought to be learnt and exploited. In the work of Bilaj et al. [2024] it is assumed that the tasks were sampled from a common distribution such that they are concentrated around an affine subspace, which is learnt through PCA algorithm. The resulting projection matrices could then be exploited to improve learning for new tasks in an adapted UCB and Thompson sampling approach.Other lines of work are Cella et al. [2020] , Kveton et al. [2021] , Basu et al. [2021] , which learns the mean of the distribution under the assumption that the covariance of the prior is known or Peleg et al.[2022] which generalizes this assumption and attempts to learn the covariance as well.The experiments have been conducted with an intel i7 CPU with 12 2.6 GHz cores and 32 GB of RAM. The two experiments with the highest number of tasks (200) and dimension (80) take about 8 hours, parallelized over the 12 cores.To generate clusters, we generate |P| variables v ii∈P from the uniform distribution, then we use them to construct a categorical distribution with probabilities proportional to e vi . These probabilities defines the cluster proportions.We implement the Primal-Dual algorithm proposed in Jung [2020] to solve the Network Lasso problem but we do not vectorize the matrices (in the sense of stacking their columns into a vector), which speeds up computation.Given two fully connected graphs weightless G 1 and G 2 with size 100 each, we progressively link them by edges, we construct the Laplcian L of the resulting graph G. We measure the minimum topological centrality index min 1≤i∈200 (L † C ) -1 ii , and the algebraic connectivity, i.e. the minimum non-null eigenvalue of L. Clearly, the minimum topological centrality index grows faster than the algebraic connectivity in this case, and seems to saturate at some level that is reached in a linear progress by the algebraic connectivity.The first limitation of the paper is the restriction to the setting of i.i.d generated action sets. This restriction is common to all papers relying on Lasso-type optimization objectives [Bastani and Bayati, 2019 , Oh et al., 2021 , Cella and Pontil, 2021 , Ariu et al., 2022 , Cella et al., 2023] . Also, we do not provide a lower bound for the regret, a challenge that we let for future work. Besides, our optimization problem is not strongly convex, which can be mitigated by adding a squared L 2 norm regularization.However, such an addition would probably drastically change the theoretical analysis.As our method can be applied to transfer knowledge between users of a recommender system, it has the potential to improve their overall experience by learning their preferences quickly. However, one must be careful with the strength of the integrated prior knowledge as it can lead to an adverse effect of slowing down the learning process.Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?Answer: [Yes] Justification: We use only simulated data.Guidelines:• The answer NA means that paper does not include experiments requiring code.• Please see the NeurIPS code and data submission guidelines (https://nips.cc/ public/guides/CodeSubmissionPolicy) for more details.• While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).• The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https://nips.cc/public/guides/CodeSubmissionPolicy) for more details.• The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.• The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only a subset of experiments are reproducible, they should state which ones are omitted from the script and why.• At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).• Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.It is possible that the notation ∥•∥2,1 denotes the sum of 2-norms of columns in the literature. 


Decision: The paper proposes a multi-task bandit algorithm which exploits the graph structure between tasks when preference vectors are piecewise constant over the graph. The algorithm solves a new optimization problem with Lasso regularization, and chooses actions greedily based on the resulting estimate which implicitly incoporates exploration. Sublinear regret is guaranteed with high probability, without the need to identify the clusters.

Contribution: A novel oracle inequality (which wasn't established even in the offline setting) is derived for estimation error of the parameter matrix estimate, which can be of independent interest.

Weakness of the paper raised by reviewers were 
- iid assumption 
- lack of comparison baselines and lack of literature review
- ambiguity of the regret bound in terms of the dependence on dimension 
- RE condition not well explained

One point that I do not agree with the reviewers is that the "iid assumption is strong". It is true that many bandit algorithms do not require this assumption, but still, existing algorithms that utilize Lasso are mostly (almost all, I think) built on this assumption. Hence, I think this should not be a decisive factor of acceptance/rejection.

However, even putting aside the comments on iid assumptions, some reviewers commonly point out the ambiguity of the current regret bound in terms of the dependence on the dimension. Authors claim that the relationship between the eigenvalue of the Gram matrix and dimension was not discussed before, but I find a paper (Kim et al., 2021) that discusses such relationship (although the definiton of eigenvalue may not be exactly the same.)
Moreover, intuitions behind many assumptions leading to the regret are not well explained.

Overall, the paper could benefit from improved presentation, including in-depth literature review, additional analysis of the dependence on dimension, and intuitive explanations behind numerous assumptions. 

Reference: Kim, W., Kim, G. S., & Paik, M. C. (2021). Doubly robust thompson sampling with linear payoffs. Advances in Neural Information Processing Systems, 34, 15830-15840.

Reviews: review: paper_summary: paper_summary: The paper introduces a multi-task contextual bandit algorithm that leverages a graph structure to model relationships between tasks. The algorithm assumes that the preference vectors of the tasks are piecewise constant over the graph, forming clusters. By solving an online network lasso problem with a time-dependent regularization parameter, the algorithm estimates the preference vectors, achieving a sublinear regret bound lower than independent task learning. Theoretical findings are supported by experimental evaluations against other graph bandit and online clustering algorithms.
strength_weakness: strength_weakness: (1) The problem setting and algorithm presented are primarily adaptations of existing works, such as Oh et al. [2021]. The main difference is the inclusion of a graph matrix in the user preference vector, but this is not the first algorithm to incorporate a graph in contextual bandits, limiting the overall novelty.

(2)  The i.i.d. assumption in contextual bandits is quite strong. Even in clustering approaches like CLUB, a conditional i.i.d. assumption is used. The current regret upper bound complexity is \(\sqrt{VT}\). There should be special cases where the algorithm can improve over \(V\) to demonstrate a more significant advantage.

(3)  Since 2019, there have been many more works on clustering in bandits. The authors should conduct a broader survey to include these more recent works and relevant baselines. Using SCLUB, which is considered outdated, as a baseline, limits the comprehensiveness and relevance of the comparative analysis.
questions: questions: What are the unique challenges in regret analysis with Lasso regularization compared to L2 regularization?
limitations: limitations: None
paper_summary: paper_summary: This paper addresses the multi-task bandit problem using graph information. The given graph represents the relationships between tasks. Assuming that the preference vector of clustered tasks is constant, the problem is formulated as a network lasso problem to estimate the lasso estimator. 
A modified restricted eigenvalue condition, commonly used in high-dimensional statistics, is defined to derive the oracle inequality for the network lasso estimator on non-i.i.d. data. The oracle inequality of the proposed network lasso estimator is derived under the assumption that the true multi-task Gram matrix satisfies the adapted RE condition.
Based on the derived oracle inequality, a greedy-type algorithm is presented, achieving $\sqrt{T}$ regret. Numerical experiments support the theoretical performance of the proposed algorithm.
strength_weakness: strength_weakness: - Since I'm not very familiar with the graph-based multi-task bandit setting, it may be that the concepts explaining the restricted eigenvalue condition (Def 2) are too heavy. It would be helpful to include comparisons or examples from existing RE conditions in high-dimensional statistics or high-dimensional contextual bandits to improve understanding.
questions: questions: 1. You mentioned that the proposed algorithm is cluster-agnostic, but if a graph representing the relationships between tasks is given, can't we identify which tasks are clustered? Compared to Gentile et al. (2014), it seems that the problem setting uses additional information. If the same information were given to Gentile et al. (2014), what advantages does the proposed algorithm have compared to not needing clustering?
2. Is the estimation error in the oracle inequality (Theorem 1) dimension($d$)-independent?
3. Can the restricted eigenvalue condition be transformed into a compatibility condition?
4. What is the definition of $\overline{Z}_P$?
5. The regret bound of high-dimensional contextual bandit using the Lasso estimator is proportional to the sparsity level (e.g., usually denoted by $s_0$) instead of the feature dimension $d$. What does sparsity correspond to in the network lasso instance, and how does it appear in the regret bound?
limitations: limitations: The authors have well-addressed the limitations in Appendix D.4 and further research directions in Section 7.

The content discussed in this paper appears to have little to no negative societal impact.
paper_summary: paper_summary: In this paper, authors work under the multi-task contextual bandit settings by representing the task correlations through the graph structure. To solve this problem, authors propose an algorithm that utilizes a linear regression formulation with Lasso constraint in terms of the node connectivity. Theoretical analysis as well as experiments against several baselines are presented to demonstrate the effectiveness of proposed method.

-	The paper is generally well-written, with crisply clear descriptions of required assumptions, and the proposed solution is intuitive and well-motivated.

-	Good empirical performances. Authors compare proposed algorithm with several clustering of bandits baselines, showing the effectiveness of the proposed method. The performance gain over existing methods is impressive. 

-	Novel theoretical analysis roadmap. Overall, the theoretical analysis pipeline is novel and the looks promising to me. With the additional introduced RE assumption, authors are able to improve the regret bound to $\tilde{O}(\sqrt{\bar{T}})$ instead of the vanilla time horizon.

-	My major question is regarding the numerous assumptions required for the theoretical analysis. For instance, in Assumption 1, authors assume the candidate arms across different arounds are generated i.i.d. from a fixed distribution. This is different from existing clustering of bandits works, where the candidate arm contexts in each round is conditioned on previous observed arms. In this case, assumption 1 is somehow deviates from the actual applications of recommender systems where the candidate arms of each round are refined along with more information collected from the environment.

-	For the experiments, authors have compared against multiple clustering of bandit works. In this case, it would be good if authors can include additional discussions comparing your theoretical outcomes with those of existing clustering of bandits works, which can offer more intuitive comparison with existing approaches.
strength_weakness: strength_weakness: Please see my comments above.
questions: questions: Please refer to my questions above.
limitations: limitations: Please see my comments above.
paper_summary: paper_summary: The authors propose to use network Lasso to learn a multi-task bandit problem with given network structure. More specifically, the network structure has pre-defined unknown clustering structure, where within each cluster all the bandit tasks share the same model. The authors propose a bandit algorithm that can learn and provide a sublinear guarantee. The key difference of this paper with GOBLin in Cesa-Bianchi et al., 2013 is that this paper uses a network Lasso (or something like a group Lasso) penalty while GOBLin use a ridge penalty.
strength_weakness: strength_weakness: 1. I think the authors need to provide more real-world examples to show why their network structure (and the correpondingly induced network Lasso bandit algorithm) is pratical, instead of stating their algorithm is good because it provides piecewise constant property in constrast to smoothness of GOBLin in Cesa-Bianchi et al., 2013. The key assumption in this paper is that the network structure is given, and the network can be splitted into connected clusters, within which the task parameters are the same. Can authors find or describe a couple of pratical examples/datasets where such a network exists, given that bandit is a very pratical problem?

2. The literature review that compare with the previous literature are not very accurate and sufficient IMO. For example, the authors mention Gentile et al., 2014 and Li et al., 2019 can cause overconfidence in constructing clusters. However, these algorithms do not have prior information about clusters such as a given network and thus they have to learn the clusters conditioned on the task similarities. In that sense, these algorithms are more pratical because oftentimes in practice network information is lacking. Here one should also add a related reference Context-Based Dynamic Pricing with Online Clustering by Miao et al., 2022. There are also robust multitask bandit algorithms (e.g., Multitask Learning and Bandits via Robust Statistics by Xu and Bastani, 2024) that can also solve the network bandit problem if the network structure follows certain assumptions; Multi-Task Learning for Contextual Bandits by Deshmukh et al., 2017 discuss a multitask bandit problem but use kernal based method. I suggest the authors add a more detailed literature review to discuss their paper's connection with these current multitask bandit algorithms. 

3. Typically, greedy algorithm (the method proposed in this paper is greedy too due to Assumption 2) has better performance in bandit simulations compared to UCB-based algorithm (see Bastani and Bayati, 2020). Therefore, it's not a fair comparison in Figure 1, where all benchmarks are UCB algorithms. I think it's necessary to add the following benchmarks: OLS-Bandit or Lasso-Bandit (Bastani and Bayati, 2020) without task sharing, and Cella et al., 2023 which use low-rank structure to do multitask bandit, and also a few others mentioned above as a benchmark to show that the network structure indeed helps, fixing the difference due to UCB and greedy algorithms.

4. I feel it's a false claim that the regret bound in Theorem 3 "doesn't depend on the dimension" and it's due to the concentration inequality from Hsu et al., 2012. Intuitively, the regret bound should depend on the dimension unless one assume that the number of tasks in a cluster is d-dependent so the regret bound is smaller compared to a typical single bandit regret bound. I think the reason why here the bound seems to be d-independent is because the dimension $d$ is hiden in the problem-dependent parameter $\phi$. Since the authors assume the context $x$ has norm 1, the minimum eigenvalue of $E[xx^\top]$ should scale as $1/d$, and hence $\phi^2$. I don't think a typical tail inequality in Hsu et al., 2012 can improve the bound regarding the context dimension. 

5. I think the asymptotic assumptions in Theorem 3 is incompatible with the finite-sample analysis in a typical bandit analysis and looks weird. I suggest the authors keep the isoperimetric ratio and centrality index as part of the regret bound (instead of forcing them out using the asymptotic assumptions), even though it might add an additional T-linear term due to the misspecification error caused by the inter-cluster edge connections. I feel that's the case because in the extreme case when each cluster has size 1, there will be misspecification error penalizing tasks connected the inter-cluster edges towards each other. I think it's totally fine to have such non-sublinear terms to provide a more comprehensive understanding of the limit of such network structures. 

I am willing to raise my rating if the authors can solve my questions and concerns.
questions: questions: See my points above.
limitations: limitations: N/A

Comments: title: About the dimension dependence and the possible linear regret (part 2)
About the dimension dependence and the possible linear regret (part 1)
Reply to the authors
Thank you for your response.
On the the iid context set generation assumption in references [3,5,6]
comment: We would like to point out that in references [3,5,6], all of which consider assumptions that are akin to ours, the dependence of $d$ in the $T$-dependent regret term is due to summing up the time-dependent regularization coefficient over time. This regularization term's choice follows from bounding their respective stochastic processes. All of their regularizations are norms ($L\_1$ and nuclear norm for the multi-task setting of [6]), whereas in our case we use a semi-norm. Hence, intuitively, the behavior of the bounds might differ. In addition to that, our semi-norm acts at the level of the nodes, not at the level of the dimension as it is the case in [6]. 

Other potential sources of dimension dependence might be the constants appearing in the relaxed symmetry and balanced covariance assumptions. However, none of such dependencies was discussed in previous work. We will point out such potential dependence.

## Potential linear reget due to misspecification

Our regret is based on a converging oracle inequality which holds with high probability. All the event probabilities required for it to hold are discussed in the proofs. The complementary events, which could potentially result in linear regret bounds, have vanishing probabilities associated with them, thus a linear term in the regret is ruled out. 

In addition, our asymptotic assumptions in the regret affect two terms: 
* Total horizon $T$, equal to $|\mathcal{V}|\bar{T}$, on which the regret depends sublinearly.
* Term $f(\mathbf{\Theta}, \mathcal{G})$ that does not have any dependence on time, hence no dependence on the horizon, and no possibility to cause a linear horizon dependence. 

Such assumptions are not made to assume that inter-cluster edges are sparse, they are made to simplify the bound for the reader, and to offer more intuition on the dependence on the graph, but cannot introduce a linear dependence, as explained for the $f(\mathbf{\Theta}, \mathcal{G})$ term. Our RE assumption, and especially the part concerning the RE-norm, accounts for the inter-cluster variations. Indeed, it involves the  $(1-\kappa)^+\Vert \mathbf{B}\_{\partial\mathcal{P}}^\dagger\mathbf{B}\_{\partial\mathcal{P}}\mathbf{Z}\Vert$ term which clearly depends on the boundary. However, for a well-behaving graph, we can assume that $\kappa>1$ (kindly refer to the response to reviewer QF4d, in which we express more intuition on this aspect), and even for $\kappa < 1$, no linear dependence is possible. Indeed, it is sufficient to examine the proof of the oracle inequality to see that it has a $\tilde O(\cfrac{1}{\sqrt{t}})$ dependence  (where $\tilde O$ hides logarithmic factors), which results in the $\sqrt{T}$ part in the regret.
We thank the reviewer for the raised issues, and we address them below.
## Dependence on the dimension
We restate that our regret does depend on the dimension logarithmically, such dependence being the result of ensuring that the restricted eigenvalue condition (Definition 2 and Assumption 4) holds for the empirical multi-task Gram matrix. The other part of the regret, the result of the oracle inequality bound, does not depend on the dimension. We kindly invite the reviewer to check our proofs in the supplementary material. To facilitate navigating through the proofs from Lemma 1 to Theorem 1, where we intentionally separated the results concerning deterministic inequalities (Lemma 1 and Lemma 2), and probabilistic ones (from Lemma 3 and Proposition 4). We provide the following explanation of every technical result's role:
    
* Lemma 1 follows from the optimality of $\hat{\mathbf{\Theta}}$ and the piecewise constant assumption on $\mathbf{\Theta}$. Indeed, the total variation norm of $\mathbf{\Theta}$ only comes from the differences between the parameter vectors across $\partial\mathcal{P}$. 
* Lemma 2 bounds the total variation of the error signal by leveraging a graph-based decomposition, stated in Proposition 2 (where we decompose the identity matrix $\mathbf{I}\_{|\mathcal{V}|}$).
* Lemma 3 relies on Theorem 2.1 of [10]. It amounts to bounding the squared Euclidean norm of $\mathbf{X}\_{\mathcal{V}}^\top\mathbf{\eta}$, where $\mathbf{X}\_{\mathcal{V}}$ is the $t \times d|\mathcal{V}|$ matrix that is block-diagonal with blocks equal to $\mathbf{X}\_1, \cdots, \mathbf{X}\_{|\mathcal{V}|}$, the matrices obtained by concatenating the row context vectors encountered for every task. This is equivalent to bounding the quadratic form $\mathbf{\eta}^\top M\mathbf{\eta}$, where $M$ is the matrix we defined in the general rebuttal response, and that has size $t \times t$ rather than $d \times d$. Now, considering any matrix square root $N \in \mathbb{R}^{t \times t}$ of the PSD matrix $M$ (i.e. verifying $N^2 = M$), we obtain 
    $$ \Vert \mathbf{X}\_{\mathcal{V}}\mathbf{\eta} \Vert^2 = \mathbf{\eta}^\top M\mathbf{\eta} = \Vert N\mathbf{\eta} \Vert^2.$$
We make use of $N$ above only because the result in [10] is stated for square matrices. Their $\mu$ vector is null as shown in the proof of Lemma 3, since $\mathbf{\eta}$ is formed of centered noise coordinates. What remains is a part that solely depends on $M$, more precisely on the trace of $M$, the trace of $M^2$, and the spectral norm of $M$. We have $tr(M^2) \leq tr(M)^2$, simply because the left-hand side is the sum of squares of $M$'s eigenvalues, and the right-hand side is the square of their sum, and these eigenvalues are all nonnegative since $M$ is PSD. The spectral norm is the maximum of the eigenvalues and can be bounded by their sum, the trace. Hence, the only dependence of the bound on $\mathbf{X}\_{\mathcal V}$ is via $tr(M)$. We have
$$tr(M) = tr(\mathbf{X}\_{\mathcal{V}}\mathbf{X}\_{\mathcal{V}}^\top) = \Vert \mathbf{X}\_{\mathbf{\mathcal{V}}}\Vert^2\_F = \sum\_{m \in \mathcal{V}}\Vert{\mathbf{X}\_m}\Vert^2\_F \leq \sum\_{m \in \mathcal{V}} |\mathcal{T}\_m(t)|^2 \leq t^2,$$
where $\Vert \mathbf{X}\_m\Vert^2\_F$ is the sum of the squared Euclidean norms of context vectors encountered by task $m$, all of which are bounded by $1$ by assumption. In comparison, bounding the stochastic process for the Lasso for example [1,2,3,5] relies on bounding the infinity norm, which introduces the dimension via a union bound.
* Proposition 4 combines Lemmas 1,2,3
* Theorem 1 is the only place where we make use of our RE assumption, that assumption introducing two constants $\phi$ and $\kappa$.
    * For $\phi$, in addition to our statement that no LASSO-type bandit paper discussed its dependence on $d$ or any other problem parameter, we point out that even in the offline learning literature studying the LASSO problem and its related problems, such a dependence is not considered. Still, we indicated that we will indeed mention a potential dependence of $\phi$ on the dimension.
    * For $\kappa$, the interval to which it belongs depends only on the structure of the graph clusters and the graph boundary.
    
Concerning the reviewer's remark about the gap-independent bounds being dependent on the dimension, in our case that would be equivalent to studying the worst case of our setting, and stating an instance-independent bound. Here, one must specify what the bandit environment class is. If the environment contains for example all of the signals that are piecewise constant on the fixed graph, then maybe a dependence on the dimension might appear, but that is not what we study.
I thank the authors for their responses and resolve some of my concerns in literature and empirical results. However, the rest of the questions are still not addressed well. 

1. I still feel the authors' explanation about the regret dependence on the dimension is doubtful. Intuitively, as long as the bound is gap-independent, i.e., O(sqrt(T)), and there're no assumptions on model, e.g., sparsity on the parameters, the bound must depend on the dimension d. It could be possible due to the sharing structure that the d cancels out with the number of tasks that share the same parameter. However, I didn't see any assumption on the relation between d and the number of tasks in a clusters. Actually, from the explanation, now I feel it's actually all relevant terms of M that implicitly contains the depedence on d, e.g., the trace of $M \in \mathbb{R}^{d \times d}$ should be proportional to d. But this is not explained anywhere clearly. 

2. My intuition about potential misspecification error that will be linearly dependent on the time T is as follows. The network structure here has both inter-cluster and intra-cluster edges. If the parameters within the same cluster are the same and the model allows heterogeneity across clusters, the penalty w_{m, n} \|\theta_m - \theta_n\|_2 will introduce extra bias if m and n do not belong to the same cluster. The trick the authors use to avoid this misspecification error is to use asymptotics assuming that inter-cluster edges are sparse. However, without this assumption and only with a static network assumption, i.e., the network is fixed, this will introduce linear term on T. I am curious after removing additional asymptotic assumptions how the authors can provide a bound that doesn't contain misspecification error, without assuming away the intra-cluster edges. 

I'm happy for further discussion but would like more clear intuition and explanations on my questions. According to the above technical concerns, which is important for a theory paper, I won't change my score for now.
I thank authors for your detailed discussion in terms of theoretical comparisons with clustering of bandit works. Although I still think it can be strong to have the i.i.d. assumption for real-world bandit learning scenarios (maybe for this series of works in Lasso Bandits), I will keep my current positive score given authors' theoretical contributions.
Thank you for your clarifications. After checking related Lasso bandit works, I see that the i.i.d. assumption is indeed used. However, I still think that this assumption should be removed in the context of the bandit problem, as it limits the exploration, which is a crucial component of these algorithms. The current approach seems more aligned with a greedy algorithm. Nonetheless, with the theoretical contributions made in this paper, I have accordingly increased the score.
Thank you for your question. The i.i.d context  generation assumption in those references are stated as follows:
* Reference [3]: at the beginning of Section 2.2 titled "Generalized Linear Contextual Bandits" (end of the third sentence there), which states: "where the tuple $\mathcal X_t$ is drawn i.i.d. over $t \in [T]$ from an unknown joint distribution with probability density $p_{\mathcal X}$".
* Reference [5]: at the beginning of Section 3.1 titled "Model and Notation" (beginning of the third sentence there),  which states: "The successive sets $(\mathcal{A}_t)\_{t \geq 1}$ form an i.i.d. sequence with distribution $p_A$".
* Reference [6]: at the last sentence of Assumption 1 under Section 3.1 titled "Stochastic Linear Contextual Bandits", which states: "We assume the tuples $\mathcal{D}_1, \cdots, \mathcal{D}_N$" to be drawn i.i.d. from a fixed unknown zero mean sub-Gaussian joint distribution $p$ on $\mathbb{R}^{Kd}$".
Thank you for the detailed responses to my questions. I have no further questions.
Thank you for your response. Can you clarify which assumption in references [3, 5, 6] corresponds to the i.i.d. arm context assumption?