Clusters Agnostic Network Lasso Bandits

• Mixing problem setting with algorithms: Since one of our main contributions is the oracle inequality itself, we have written the network lasso problem in the problem setting. However, since our paper is a bandit algorithm paper, we can move that optimization problem to the algorithms section.
• Referring to elements of $\mathcal{V}$ by tasks or users: As it is mentioned in the introduction section, each task represents a user in our motivating example of an e-commerce website. We will also add a sentence indicating that we use the terms 'task' and 'user' interchangeably.
• The setting being agnostic to the graph: We respectfully disagree with the reviewer since the graph is given as part of the problem setting and it is used in the optimization framework in Equation (2) via the regularization term defined by edges and weights. The setting is agnostic to the cluster structure i.e. the agent is not explicitly aware which users belong to which clusters. It utilizes side information in the form of a given graph by using the network lasso regularization in order to implicitly learn the cluster structure. This type of approach is common when it comes to multi-task bandit problems with side information (e.g. [16,17]).
• The choice of network lasso being unjustified: We respectfully disagree. Indeed, the network lasso problem is a well-known choice when one is given a graph and wants to estimate a piecewise constant signal over that graph [12,13,14]. Our choice is analogues to choosing the LASSO estimator when dealing with high dimensional sparse preference vectors $\theta$ in the single task case [1,2,3,5]
• Absence of dependency on dimension $d$: We respectfully disagree and point out that our regret bound indeed depends on the dimension $d$. In Theorem 3 we have the term $\log(|\mathcal{V}|d)$ as part of the overall regret. Even in the case of $|\mathcal{V}|=1$, we would still have a $\log(d)$ dependence.

6. Comparing the regret bounds of the proposed approach in this paper with those of the relevant baseline methods: Our regret bound does not depend on the number of clusters, but rather on other properties of the graph such as the worst topological centrality index and the size of the boundary. In general, the bounds are incomparable, due to our high reliance on the graph. To make the number of clusters appear, we can make some additional assumptions:
   • We assume that the algebraic connectivity of a cluster $|\mathcal{C}|$ is $\Omega(|\mathcal{C}|)$. This holds for example for fully connected clusters having an algebraic connectivity equal to their size. As a result, from Proposition 3 of the appendix, the topological centrality index of such cluster $\mathcal{C}$ behaves as $\Omega(|\mathcal{C}|)$.
   • For a weightless graph, for each cluster, its vertices linking it to the outside have a number at most equal to the number of edges linking them to the boundary. Hence, we can bound the isoperimetric ratio as follows: $\max_\mathcal{C}\iota(\mathcal{C}) = \max_\mathcal{C}\frac{|\partial_v\mathcal{C}|}{|\mathcal{C}|} \leq 2\frac{w(\partial \mathcal{P})}{\min_{\mathcal{C}}|\mathcal{C}|}$ With such assumptions, we have

$\sqrt{\frac{\max_\mathcal{C}\iota(\mathcal{C})}{\min_\mathcal{C}c(\mathcal{C})}} \leq \sqrt{2}\frac{\sqrt{w(\partial\mathcal{P})}}{\min_\mathcal{C}|\mathcal{C}|}.$ where $|\mathcal{P}|$ is the number of clusters. As a result, the horizon-dependent part of the regret in Corollary 1 grows as $\tilde O\left(\sqrt{\overline{T}|\mathcal{V}|} + \frac{w(\partial\mathcal{P})}{\min_\mathcal{C}|\mathcal{C}|}\sqrt{\overline{T}|\mathcal{V}|}\right)$. The minimum cluster size has a substantial influence on the performance in this case. Since it appears in the denominator, we need an assumption that it behaves as $\Omega(\frac{|\mathcal{V}|}{|\mathcal{P}|})$. As a result, the last big $\tilde O$ term becomes $\tilde O\left(\sqrt{\overline{T}|\mathcal{V}|} + \frac{w(\partial\mathcal{P})}{\sqrt{|\mathcal{V}|}}|\mathcal{P}|\sqrt{\overline{T}}\right)$. Thus, when the number of clusters is less than the dimension, we have a linear dependence in the rank of the preference vectors matrix via the $|\mathcal P|$ term.

• Compared to the $\tilde O(\sqrt{r\overline{T} |\mathcal V| d}) + |\mathcal V| \sqrt{r\overline{T}})$ regret of [6], our linear dependence on the rank is better as the dependence of [6] is in $\sqrt{rd}$. This should not be surprising since in our setting, the graph provides additional information that guides the estimation of these dimensions better than without it.
• Compared to the $\tilde O(\sqrt{r\overline{T}|\mathcal{V}|})$ of [7], their bound seemingly has a better dependence. However, one must take into account two observations about Theorem 5.4 of [7] that states the regret bound:
  • the regret bound holds with a probability at least $O(1-\delta - d^{-10})$, with the stated bound being independent of $d$. Hence, seemingly the result gets better when one increases the dimension.
  • Looking closer at the proof of Theorem 5.4 of [7], one can see that the regret is bounded by the quantity $\mathcal{G}\_{m} - \mathcal{G}\_{m-1}$. This quantity is assumed in that theorem to be $\Omega(d)$, and it is bounded by the number of rounds per task. This implies that the number of rounds per task is $\Omega(d)$. However, in our paper, we do not assume any relation between the horizon and the dimensionality.

1. Relaxed symmetry and balanced covariance assumptions in Assumption 2, and their impact on the practical applicability of the method: These are technical assumptions that [3] proposed for the first time, and that [4,5] also used in their analysis, with [5] studying a multi-task setting. According to [3], both assumptions are satisfied for several probability distributions. Whether weaker assumptions can be used to generalize to real-world data distributions is an open question worth considering.

2. The approach being advantageous only when the number of clusters exceeds the dimension: We did not mention anywhere in our paper that the only justification for this approach is when the number of clusters exceeds the dimension $d$. Our approach is useful when there is an available graph representing side information that helps in accelerating learning. Had the graph not been available, other approaches leveraging the low rank structure would of course be more interesting. In other words, our work is about leveraging the available graph's stucture conveniently. 2.a Difference from of improvement upon low-rank multi-task learning methods when the number of clusters exceeds d: As we mentioned in the appendix, the rank of the matrix of feature vectors in our case is at most equal to $\min(|\mathcal{P}|,d), which is equal to$d$ when the number of clusters exceeds the dimension. 2.b Example where the number of clusters is more than the number of dimensions: We think that such a setting makes sense if we want to group the users of an e-commerce website for example due to storage constraints. The dimension can be reduced via some preprocessing step, leading to it being less than the number of clusters.

3. The experimental setting being restricted to the case where the dimension is higher than the number of clusters : Nowhere in the paper have we claimed that our algorithm is only applicable to the low-rank setting. In fact, it can very well be applied in the case that the number of clusters exceeds the number of dimensions. We chose the low-rank setting to showcase the advantageous dependence on the dimension, guaranteed by our regret bound. Even though [6] corresponds to the low-rank setting, our algorithm surpasses the TraceNorm approach as it leverages the available graph conveniently 3.a Experimental comparisons with low-rank multi-task learning methods for the scenarios presented in Figure 1: First, we insist that our goal is not to solve the multi-task setting with a low rank, but to conveniently leverage a graph encoding similarities between tasks when it is available and when the tasks signal is constant over it. Second, we included a comparison to the TraceNorm policy of [6] in our paper, and we do not find any online implementation of [7]. Moreover, we think that [6] is the best low-rank approach to compare to as it uses the same type of assumptions we have in our work (RE/RSC condition, relaxed symmetry, balanced covariance ...) and similar proof techniques. 3.b Experiments where the number of clusters exceeds $d$: We provide two sets of additional experiments with $d=2, |\mathcal{P}| = 20$ and $d=10, |\mathcal{P}| = 25$ in a new appendix section D.4, in the revised version, that we write in blue. Both of these cases do not correspond to the low-rank setting, and we can see that our algorithm still outperforms the low-rank approach of [6].

4. Comparison with the low-rank multi-task learning results presented in Yang et al. and Lin et al., given that all the plots in Figure 1 correspond to a low-rank case: Kindly refer to our answers to questions 3.a and 3.b.

5. Comparing the proposed approach with the low-rank multi-task learning results specifically for settings where the number of clusters exceeds the problem dimension: Kindly refer to our answer to question 3.b.