Adaptive Sample Sharing for Multi Agent Linear Bandits

We would like to thank the reviewer for their positive and constructive comments. Below, we address your concerns and provide detailed answers to your questions.

1/ The orange ellipsoid (representing the collaborative estimation) corresponds to a reduced estimation variance, as it yields a smaller Mahalanobis radius of the confidence ellipsoid—note that the smaller ellipsoid might not be contained in the bigger one, we will provide a more general illustration to underline that. However, notice that the center of the orange ellipsoid differs from that of the blue ellipsoid due to the introduced bias, illustrating the bias (OLS estimate deviation) - variance (confidence ellipsoid radius reduction) tradeoff.

2/ We will add a section in the appendix to properly detail the steps to obtain Table 1 from Theorem 6.4 and Lemma 6.1. The proof is similar to CLUB and SCLUB, and the improvements stem from both the Mahalanobis separation criterion and a refined analysis from Abbasi-Yadkori et al 2011.

3/ The definition of $\nu$ remains unchanged across all theorems: it is the regret upper bound without sample sharing. Considering the upper bound of Theorem 6.4, the first term corresponds to the regret minimization improvement due to the variance reduction (represented by $\mu$) and the second term corresponds to the cost of sharing (i.e., the shared OLS estimate bias, due to misassigned agents). This second term features an interplay between the determinant and the exponential term in $n_i^e(t)$, which overall results in a $\mathcal{O}(\frac{4L}{\delta \rho_{\min}\sqrt{T}^{\gamma^2R^2 - 1}})$ regret. This leads to an overall behavior of the upper bound in $\mathcal{O}(\sqrt{T} \log (T/d))$ as depicted in Table 1.

4/ Thank you for pointing out the inconsistency in the appendix content table; we will revise the naming of the appendix sections accordingly.

5/ To derive a lower bound on the cumulative pseudo-regret, we consider the optimal case of $N$ collaborative agents sharing the same bandit parameters, forming a single—known—cluster. This leads to: $\frac{1}{N}\mu(\delta, T) \leq R_{i,0,T}^{\mathrm{cluster}}$. We will further compare the additional terms stemming from the clustering estimation in the upper bound of Theorem 6.4 to this lower bound to underline the cost of clustering.

6/ As defined by in [1], pseudo-regret uses expected rewards, while regret uses realized rewards; for our paper we use Bubeck’s definition.

7/ Thank you for pointing out the typo in Table 1: the proper constant term should be $d\sqrt{\frac{M}{N}}$ for CLUB and SCLUB which is equivalent to $\frac{d}{\sqrt{\rho_{\min}N}}$ for balanced cluster sizes. As mentioned in 2/, the differences ($\sqrt{d}$ factor and $T/d$ in the logarithm) are due to the use of a Mahalanobis metric combined with a refined analysis (i.e., applying the Elliptical Potential lemma on the design matrix $\mathbf{A}_i$).

[1] Bubeck, S., & Cesa-Bianchi, N. (2012). Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations and Trends® in Machine Learning, 5(1), 1-122.

Additional comments:

If you have any additional questions about the paper and the theoretical and empirical analysis, we would be happy to provide further clarification.

Please let us know if you need any additional information, clarification or modification that we could provide for you to improve your score.

We would like to thank the reviewer for their very positive and insightful comments. Thank you very much for your kind appreciation of the paper's results.

Thank you for the suggestion regarding the structure of the paper; we will revise it, as we agree it improves the overall logical flow.

Additional comments:

If you have any additional questions about the paper and the theoretical and empirical analysis, we would be happy to provide further clarification.

We would like to thank the reviewer for their positive and constructive comments. Below, we address your concerns and provide detailed answers to your questions.

1/ Thank you for the remark; we will revise the structure of our paper, as we agree it improves the overall logical flow.

2/ There is indeed a challenge in analyzing the effects of asynchronous pulling. It leads to differently shaped ellipsoids and requires a rescaling term in the form of $\mathbf{A}_i^{-1} \mathbf{A}_j$, which makes the proof much more difficult. Therefore, we restrict our analysis to the synchronous setting. In Definition 5.1, we use the general case because this definition is used in the practical implementation of the algorithm, which allows for empirical evaluation of our method in the asynchronous setting.

3/ Thank you for pointing out this typo: the correct definition consider the minimum w.r.t $s$ and compare the later to 0:

\Psi(i, j, t) = \mathbf{1}\left \\{ \min_{s \in ]0, 1[} \frac{\gamma^2}{4} - \sum_{l=1}^d \mu_{tl}^2 \frac{s (1 - s)}{\beta_{i,t}^2 + s (\beta_{j,t}^2\eta_{tl} - \beta_{i,t}^2)} < 0 \right\\} \enspace.

We will correct this and update the corresponding subscripts.

4/ The graph $\mathcal{G}_t$ is updated and stored in a central server that first requests the design matrix and the regressand of each agent in the neighborhood of agent $i$. Then, send collaborative OLS variables to agent $i$ to pull an arm. Hence the neighborhood is determined by a central server to manage the sampling sharing logic within the agents network. Note that our work focuses on sample efficiency rather than communication; however, sample sharing for a general decentralized setting is a promising line of future work.

Additional comments:

If you have any additional questions about the paper and the theoretical and empirical analysis, we would be happy to provide further clarification.

We would like to thank the reviewer for their positive and constructive comments. Below, we address your concerns and provide detailed answers to your questions.

1/ We will add a specific section in the appendix, featuring a flow-chart, where we will better expand the description of the algorithm major steps: a/ the samples sharing (L 2-4), b/ the UCB pulling (L 5-6), c/ the local variables update (L 7) and d/ the graph $\mathcal{G}_t$ update (L 9).

2/ The focus of this paper is to analyze the effect of sample sharing on regret minimization in the general case—i.e., without any assumption on the agent clustering structure. To that end, we ignore considerations such as communication cost. However, for completeness, we will add a section in the appendix presenting the empirical communication cost in the federated setting (using a central server), along with a theoretical upper bound in the case where the clustering structure is assumed (since in that setting, the number of agents per cluster can be quantified).

3/ The term $\beta(\delta, \mathbf{A}_t)$ is stated in Theorem 4.1 and corresponds to the confidence ellipsoid radius of the OLS estimate. We will restate and clarify the definition of $\beta(\delta, \mathbf{A}_t)$ in Theorems 5.1, 6.1, 6.2, 6.3, and 6.4, and underline that the definition of $\nu$ remains unchanged across these theorems.

4/ A particularity of the sample sharing problem is that it unfolds in two distinct phases: one where sharing is beneficial, and another where independent parameter estimation is preferable. Theorems 6.2 and 6.3 present the cumulative regret at the transition point between these phases, highlighting the gain from sharing before switching to an independent regime. Table 1 reports the asymptotic regret in the independent setting, after collaboration has ceased. Thus, the results of Theorems 6.2 and 6.3 cannot be presented in the same form. However, the upper bound can be summarized as a tradeoff between the acceleration of the first term (in $\mu$), compared to the independent regret ($\nu$), and the bias from data sharing, captured in the second term.

5/ The other algorithms perform poorly in terms of clustering. Rather than accurately recovering the cluster structure, other approaches focus on regret minimization, either by design or by regret-oriented hyperparameter optimization. Figure 8 in Appendix R.3 shows the progressive degradation of the clustering score. Notably, no existing work in the literature provides theoretical guarantees or empirical validation regarding the quality of the clustering.

6/ Beyond the analysis of sample sharing itself, the most significant aspect to revise is the use of the Euclidean distance criterion (as in Gentile et al. (2014); Ban & He (2021); Wang et al. (2023)), which is effectively equivalent to the test proposed by Gilitschenski et al. (2012), where the ellipsoids considered are $\mathcal{E}(\hat{\mathbf{\theta}}_i, \lambda^{\min}(\mathbf{A}_t)\mathbf{I}, \tilde{\beta})$ and $\mathcal{E}(\hat{\mathbf{\theta}}_j, \lambda^{\min}(\mathbf{A}_t)\mathbf{I}, \tilde{\beta})$ thereby ignoring most of the arm-pulling history.

7/ We will add a summary table in the appendix outlining the different clustering assumptions considered in the literature and mentioned in our related work:

• no assumption: our paper, except in “Regret analysis with clustered parameters”.
• same bandit parameter within a cluster: our paper with Assumption 6.1.
• same bandit parameter within a cluster and a minimum distance between clusters: Gentile et al. 2014, Li et al. 2016, Li & Zhang, 2018, Wang et al. 2023, Yang et al. 2024.
• close bandit parameters within a cluster and overlapping clusters definition: Ban & He 2021.

Note that our primary intention is to derive a principle rule to share samples between agents without introducing assumptions on their distribution. We then extend our results to the clustered setting to provide a fair comparison to existing work.

8/ In the synchronous setting, all agents in a cluster select an arm based on the same shared history. Since UCB is a deterministic rule, two agents using the same history will select the same arm. Therefore, their design matrices will also be identical. We will add an additional section in the appendix to better explain this aspect of our setting.

Additional comments:

If you have any additional questions about the paper and the theoretical and empirical analysis, we would be happy to provide further clarification.

Please let us know if you need any additional information, clarification or modification that we could provide for you to improve your score.