Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper considers a linear contextual bandits problem in a federated setting where different users have different contexts but the rewards are generated through common global parameters. The goal is to minimise the regret for each user while sharing the exploration across users. The paper proposes an algorithm termed Fed-PE with regret bounded as O(\sqrt{dMT}), where d is the dimension of contexts, M is the number of users and T is the time-horizon. A matching lower bound is also presented showing that this regret is tight. The main challenge in this setting is to \emph{balance} the exploration across users as contexts might be very diverse. In order to address this challenge the paper proposes a new G-optimal design which optimises for balanced exploration across users. 
main_review: Even though there is a burgeoning literature on federated/distributed settings for linear bandits, the setting considered in this paper is new, interesting and well motivated. I think the technical contributions of this paper are also sound. I like the idea of G-optimal design and its integration with a policy that only updates O(log T) times.  

Additional comments:

1. Arm Elimination: The current algorithm successively eliminates arms over time for each user. Is it possible to design an algorithm in this setting that does not eliminate arms over time similar to the UCB algorithm for non-contextual bandits?  

2. Shared contexts across users: The current algorithm does not take advantage of the fact that some contexts across users might be similar. For example, there might be just m different "generic types" of users and each user might be from one of these types. In this case the dependence on M may be replaced with the dependence on m. Is it possible to do this in a more data dependent way, i.e. by designing an algorithm that automatically detects shared contexts?


limitations_and_societal_impact: The paper argues that their algorithm is "private to some extent" as the context vectors are not sent to server, but I am not quite satisfied with this claim as a simple transformation of the context vectors is anyways sent to the server.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The paper studies a federated setup where each client faces a stochastic contextual bandit.  The parameters of the bandits are coupled across the clientsm. The clients share their local estimates with the server which aggregate them and share back with the clients. The client are hetogenous and the server leverages the geomereic structure of the linear rewars to facilitates the clients learn the optimal arms.  Authors propose a collaborative algorithm called Fed-PE that do not require the nodes to exchange the local feature vectors thus preserving the privacy of the nodes. The authors consider the cases where the paramers are disjoint across the arms or coupled. The performance of the algorithms are valued on both synthetic and real datasets. 
main_review: The problem of contextual bandits in a federated setup is interesting. The authors' attempt to model this problem and analysis is appreciable. 
However, the way the problem is motivated and it is modeled is not consistent. 

--In the motivational applications of personalized content recommendation and personalized online education, the contexts are dervied from the user profile, and for different users, the context can be different. But in the model, contexts are fixed. Should not the context be allowed to change in each round? 

--Is $f^p$ input to the algorithm? How is it set?

--Line 198:  It is unlcear why $\overline{e}_{i,a}$ in range$(x_{i,a})$

----

Post rebuttal:

The authors said "we consider a multi-client model, where each client is associated with a fixed user profile. The variation of contexts is captured over clients as opposed to overtime. we consider a multi-client model, where each client is associated with a fixed user profile."

This part of the motivation to model is not satisfying. If there is one learner for each profile, one has to consider a large number of learners as the number of profiles can be arbitrarily large. Also, in practice, I do not anticipate there will be one learner for each profile in applications like personalized content recommendations. The whole point of learning in personalized content recommendations is to figure out optimal action for (possibly) unseen profiles. This motivation of one learner per profile does not sound unsatisfying.

I keep my score unchanged.
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper discusses the federated multi-armed bandit problem with linear reward functions. The formulation utilizes a linear structure with agent-dependent contexts to model differences between agent reward functions. The authors propose an algorithm based on a multi-agent G-optimal design with competitive theoretical performance under heterogeneity. The authors additionally establish minimax rates under a reasonable collinearity assumption. The algorithms FedPE and Enhanced FedPE additionally provide competitive experimental performance on both simulated and real-world benchmarks. In summary, the paper is a good contribution, however, there are some issues that I would like to see addressed as well.
main_review: Originality: I believe the primary novelty of the paper is to present a linear formulation of heterogeneity across agents for the federated multi-armed bandit problem and then proposing a variant of G-optimal design. Currently, the paper is positioned (and compared against) federated contextual bandit algorithms (where the decision set changes with each iteration), whereas IMHO the paper is more suitable as a context-free formulation that essentially uses this linear formulation to account for heterogeneity within the different agents. The subsequent contributions (algorithm design, minimax rates with collinearity) all follow more smoothly from a conceptual POV if viewed from this lens, instead of a "contextual" premise. I have discussed the "contextual" aspect more in the "Issues/Concerns" section below as well.

Given the above consideration, I believe the paper has a good set of contributions from an algorithmic perspective with accompanying theoretical guarantees (based on a skim of the appendix, the proof technique is primarily a modification of the existing G-optimal route). I believe that a log T-style regret bound can also be derived by assuming a minimum gap of $\Delta$ between the rewards of the best and second-best arms for all agents, allowing us to compare more directly with multi-armed algorithms. Furthermore, the current analysis provides a worst-case regret bound, which incurs a factor of $O(\sqrt{K})$ regardless of the parameters $\theta$, but it would be interesting if the authors proposed a hybrid "smooth" model, where one can interpolate between "shared" parameters and distinct parameters with an interpolating regret bound.

Clarity: The paper is well-written and easy to understand, although I would recommend proofreading to iron out typos and some grammatical issues (minor).

Significance: There is a lot of interest in the federated/distributed bandit case, and this paper will be relevant to that sub-community.

Issues/Concerns:
- "Contextual" bandits setting: The authors incorrectly describe their setting as "contextual" whereas their setting is clearly the stochastic linear bandit setting. This is not "contextual" as the set of contexts are fixed and do not vary with time (Lattimore and Szepesvari, 2020, Chapter 20 clearly makes this distinction by calling it "Stochastic Linear Bandits" instead of "contextual"). This may seem like a nitpick, but it makes the setting considered in the paper much clearer.

- Comparison with Dubey and Pentland (2020): The regret bound presented in the former paper (Theorem 1 and Corollary 1) involves an $\mathcal O(M\sqrt{T}/\varepsilon)$ term that arises due to the $(\varepsilon, \delta)$-DP privacy guarantee, and not because of inefficiency in communication. A fair comparison would therefore be to set their FedUCB algorithm to work with no DP guarantee, i.e., $\varepsilon \rightarrow \infty$, in which case the bound is $\widetilde{\mathcal O}(\sqrt{dMT})$. Furthermore, I do not see any comparisons with FedUCB in the experiments?

- Multi-armed bandit baselines/literature review: I feel that the federated (context-free) bandit literature is also relevant as both baselines (say federated UCB1 without contexts) and part of the related work.

limitations_and_societal_impact: One limitation that the authors have to be clear about is that while this setting is indeed linear, it assumes a multi-armed environment with a fixed set of arms, which makes it inapplicable for many real-world federated learning settings such as federated recommendation systems, where the set of contexts changes with time and G-optimal design is not applicable. The authors should address this in their paper.

I do not foresee any direct societal consequences from this paper, but the authors do not discuss this either.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: I think the paper sufficiently characterizes the federated linear contextual bandits problem (i) it proposes an algorithm for both the shared parameter and disjoint parameter setting (ii) proves regret guarantees and (iii) characterizes a reasonable class of policies for which a lower bound holds; this lower bound shows that the achieved regret guarantees are near optimal. The communication cost of the algorithm is also reasonable w.r.t to prior work. I think the writing of the paper can be improved in some areas and some technical points need to be explained more, but over all I think this is a good paper. 
main_review: Pros.

1. The paper characterizes the problem almost completely providing algorithms, regret upper bounds and lower bounds for a class of policies.
2. The algorithm uses the well known D-optimal design phased algorithm from Lattimore and Szepesvari, however I think several small innovations are required to make it work in the federated setting where the context vectors are different for each agent and can potentially span different subspaces of R^d. I find the discussion in section 4.1 useful.
3. It seems that the paper also develops a new block coordinate ascent algorithm to solve the multi-agent G-optimal design problem (it is a quite natural extension to G-optimal design). Unfortunately I did not check the derivation as it has been pushed to the appendix, but this also seems like a good contribution.
4. I am quite intrigued by the class of policies in the lower bound. It seems that if we stay within this class the regret bounds are almost tight. I would still need to gain more intuition for this result (see below).

Cons and Clarification needed.

1. In the introduction it would be better if the authors choose one of the applications for example the content recommendation one and maps each of the problem details like thetas, x's and rewards to real world objects in that problem. In my experience this always makes it easier to understand the relation of the problem to the applications.

2. The model is listed as one of the contributions. Is the model in the FedUCB paper different from the shared parameter setting? -- please clarify this. I know that they are interested in DP but my question is wrt the model alone.

3. It seems that because of the differential privacy constraint the FedUCB paper achieves a worse dependency of d^{3/4} but table 1 lists a sqrt{d} dependence for this paper. Am I misunderstanding the result of the FedUCB paper?

4.  I am not an expert in federated learning so this might be a naive question. In line 139 it says that the communication cost is measured in terms of number of scalars communicated. But it seems that if the size of each such scalar is unlimited one might be able to encode a lot of information in each of them using a coding scheme. Should this not be restricted?

5. I understand from context what f_p is but can you please point me to where this is first defined in the paper? I seem to have missed it.

6.  In the original G-optimal design based algorithm if the elimination criterion is in terms of optimality gap being larger than 2^{-l} in phase l. However, here it is changed to UCB < LCB kind of a condition. What is the intuition or reason behind this? Is this mentioned in the paper?

7.  I think a little more discussion is needed about the "rank-preserving" condition. To me it seems that we are just ensuring that the rank is same, however can the subspace spanned by the LHS and the RHS be completely different?

8. I am not being able to gain a lot of intuition about collinearly-dependent policies from the text description. I think it is really important to explain this part well. I am confused by the fact that in def 1 we require this to hold for just "an arm a" and also one specific subset "S". However, in the next paragraph it is claimed that "Intuitively, for
two clients that are not collinear, their local observations on ""any"" arm a cannot be utilized to improve
each other’s knowledge of their own local models". Please add more details about why this follows.

9. Each client initially starts by pulling each arm once. This might be reasonable for the disjoint parameter case. For the shared parameter setting this is not a good idea when K is very large. For instance the original G-optimal algorithm starts by pulling a set of arms of size only d(d+1)/2. I think this needs to be incorporated in the shared param setting.
limitations_and_societal_impact: I think the authors have adequately addressed the limitations and societal impact.
review_title: null

Meta-review: During discussion, all reviewers agreed that though the motivation for the precise setting is unclear, the paper makes good technical contributions and so I am recommending the paper for acceptance. However, I ask the authors to incorporate a discussion on the assumptions of each client serving one user and possible extension to potential new users entering the system.
Decision: Accept (Poster)