Incentivized Communication for Federated Bandits
Authors: Zhepei Wei
Chuanhao Li
Haifeng Xu
Hongning Wang
Venue: NeurIPS 2023 poster (2023)
Keywords: contextual bandit
federated learning
incentive mechanism
TL;DR: We introduce a novel incentivized communication problem for federated bandits, where the server must incentivize clients to share data; The proposed solution Inc-FedUCB enjoys near-optimal regret, with guarantees on communication and incentive costs.

Abstract: Most existing works on federated bandits take it for granted that all clients are altruistic about sharing their data with the server for the collective good whenever needed. Despite their compelling theoretical guarantee on performance and communication efficiency, this assumption is overly idealistic and oftentimes violated in practice, especially when the algorithm is operated over self-interested clients, who are reluctant to share data without explicit benefits. Negligence of such self-interested behaviors can significantly affect the learning efficiency and even the practical operability of federated bandit learning. In light of this, we aim to spark new insights into this under-explored research area by formally introducing an incentivized communication problem for federated bandits, where the server shall motivate clients to share data by providing incentives. Without loss of generality, we instantiate this bandit problem with the contextual linear setting and propose the first incentivized communication protocol, namely, Inc-FedUCB, that achieves near-optimal regret with provable communication and incentive cost guarantees. Extensive empirical experiments on both synthetic and real-world datasets further validate the effectiveness of the proposed method across various environments.

Incentivized Communication for Federated Bandits
Zhepei Wei! Chuanhao Li Haifeng Xu²
Hongning Wang'
University of Virginia' ftqf5qb, c15ev, hw5x) idduuiiiii.eeuu laifenggxu@chiago..ee
University of Chicago"
Abstract
Most existing works on federated bandits take it for granted that all clients are altruistic about sharing their data with the server for the collective good whenever needed. Despite their compelling theoretical guarantee performance and com- munication efficiency, this assumption is overly idealistic and oftentimes violated in practice, especially when the algorithm is operated over self-interested clients, who are reluctant to share data without explicit benefits. Negligence of such self- interested behaviors can significantly affect the learning efficiency and even the practical operability of federated bandit learning. In light of this, we aim to spark new insights into this under-explone research area by formally introducing an incentivized communication problem for federated bandits, where the server shall motivate clients to share data by providing incentives. Without loss of generality, instantiate this bandit problem with the contextual linear setting and propose the first incentivized communication protocol, namely, INC-FEDU near-optimal regret with provable communication and incentive cost guarantees. Extensive empirical experiments on both synthetic and real-world datasets further validate the effectiveness of the proposed method across various environments.
that achieves
Introduction
Federated bandit learning has recently emerged as promising new direction promote the applica- tion bandit models while preserving privacy by enabling collaboration among multiple distributed 37 The main focus in this line of research is on devising communication-eeficieen efficient protocols achieve npar-optimal regret in various settings. Most notably, the direction on federated contextual bandits has been actively gaining momentum, since the debut of several benchmark communication protocols for contextual linear bandits in the P2P [18] and star-shaped [40) networks. Many subsequent studies have explored diverse configurations of the clients' and environmental modeling factors and addressed
clients [10 40 22 33
23
24
25
15
communication-
challenges arising in these contexts.
Notable recent advancements include extensions to asynchronous linear bandits 22 13
generalized
liner bandits 23), and kernelized contextual bandits 24 25
Despite the extensive exploration of various settings, almost all existing federated bandit algorithms rely on the assumption that every client in the system is willing to share their local data/model with the server, regardless of the communication protocol design. For instance, synchronous protocols [40] 23 require all clients to simultancously engage in data exchange with the server in every communication round. Similarly, asynchronous protocols [22] 25| [3] also assume clients must participate in communication as long as the individualized upload or download event is triggered, albeit allowing interruptions by external factors (e.g., network failure).
In contrast, our work is motivated by the practical observation that many clients in federated system are inherently self-interested and thus reluctant to share data without receiving explicit benefits from the server [16]. For instance, consider the following scenario: recommendation platform
Equal Contribution
37th Conference on Neural Information Processing Systems (NeurIPS 2023).

---

(server) wants its mobile app users (clients) to opt in its new recommendation service, which switches previous on-device local bandit algorithm to federated bandit algorithm. Although the new service is expected to improve the overall recommendation quality for all clients, particular clients may not be willing to participate in this collaborative learning, as the expected gain for them might not compensate their locally increased cost (e.g., communication bandwidth, added computation, lost control of their data, and etc). In this case, additional actions have to be taken by the server to encourage participation, as it has no power to force clients. This exemplifies the most critical concern in the real-world application of federated learning [16). And a typical solution is known as incentive mechanism, which motivates individuals to contribute to the social welfare goal by offering incentives such as monetary compensation.
While recent studies have explored incentivized data sharing in federated learning 30 38 most of which only focused on the supervised offline learning setting [[6]. To our best knowledge, ours is the first work that studies incentive design for federated bandit learning, which inherently imposes new challenges. First, there is lack of well-defined metric to measure the utility of data sharing, which rationalizes a client's 's participation. Under the context of bandit learning, we measure data utility by the expected regret reduction from the exchanged data for each client. As a result, each client values data (e.g., sufficient statistics) from the server differently, depending on how such data aligns with their local data (e.g., the more similar the less valuable). Second, the server is set to minimize regret across all clients through data exchange. But as the server does not generate data, it can be easily trapped by the situation where its collected data cannot pass the critical mass to ensure every participating client's 's regret is close to optimal (e.g., the data under server's possession cannot motivate the clients who have more valuable data participate). To break the deadlock, we equip the server to provide monetary incentives. Subsequently, the server needs to minimize its cumulative monetary payments, in addition to the regret and communication minimization objectives as required by federated bandit learning. We propose a provably effective incentivized communication protocol, based on a heuristic search strategy to balance these distinct learning objectives. Our solution obtains near-optimal regret (ld log T') with provable communication and incentive cost guarantees. Extensive empirical simulations on both synthetic and real-world datasets further demonstrate the effectiveness of the proposed protocol in various federated bandit learning environments.
Related Work
Federated Bandit Learning One important branch in this area is federated multi-armed bandits
(MABs), which has been well-studied in the literature [27] 36 19 4 20
28
32
39
34
33 43). The
other line of work focuses on the federated contextual bandit setting 18 40 which has recently
attracted increasing attention. Wang et al. 40 and Korda et al. [8 are among the first to investigate
this problem, where multiple communication protocols for linear bandits I 26 in star-shaped and
P2P networks are proposed. Many follow-up works on federated linear bandits [10 [5] [2] [3] have emerged with different client and environment settings, such as investigating fixed arm set [5]. incorporating differential privacy [10), and introducing asynchronous communication [13] 22
Li et al. [23] extend the federated linear bandits to generalized linear bandits M. And they
further investigated federated learning for kernelized contextual bandits in both synchronous and
asynchronous settings 24 25
In this work, we situate the incentivized federated bandit learning problem under linear bandits with time-varying arm sets, which is a popular setting in many recent works 40
10. 22 13]. But we do not assume the clients will always participate in data sharing: they will choose not to share their data with the server if the resulting benefit of data sharing is not deemed to outweigh the cost. Here we need to differentiate our setting from those with asynchronous communication, e.g., Asyn-LinUCB [22]. Such algorithms still assume all clients are willing to share, though sometimes the communication can be interrupted by some external factors (c.g., network failure). We do not assume communication failures and leave it as our future work. Instead, we assume the clients need to be motivated to participate in federated learning, and our focus is to devise the minimum incentives to obtain the desired regret and communication cost for all participating clients.
Incentivized Federated Learning Data sharing is essential to the success of federated learning 30), where client participation plays crucial role. However, participation involves costs, such as the need for additional computing and communication resources, and the risk of potential privacy breaches, which can lead to opt-outs [5] 14] In light of this, recent research has focused on investigating
2

---

incentive mechanisms that motivate clients to contribute. rather than assuming their willingness to participate. Most of the existing research involves multiple decentralized clients solving the same task, typically with different copies of IID datasets, where the focus is on designing data valuation On the other hand, Donahue et al. 7 study voluntary participation in model-sharing games, where clients may opt out due to biased global models caused by the aggregated non-IlI datasets. More recently, Karimireddy ct al. [66] investigated incentive mechanism design for data maximization while avoiding free riders. For detailed discussion of this topic, we refer readers to recent surveys on incentive mechanism design in federated learning [4 38
methods that ensure fairness or achieve specific accuracy objective 35 41 [].
However, most works on incentivized federated learning only focus on better model estimation among fixed offline datasets, which does not apply the bandit learning problem, where the exploration of growing data is also part of the objective. More importantly, in our incentivized federated bandit problem, the server is obligated to improve the overall performance of the learning system, i.e., minimizing regret among all clients, which is essentially different from previous studies where the server only selectively incentivizes clients to achieve certain accuracy 35 or to investigate how much aceuracy the system can achieve without payment [16].
Preliminaries
In this section, we formally introduce the incentivized communication problem for federated bandits under the contextual linear bandit setting.
3.1 Federated Bandit Learning
We consider learning system consisting of (1) N clients that directly interact with the environment by taking actions and receiving the corresponding rewards, and (2) a central server that coordinates the communication among the clients to facilitate their learning collectively. The clients can only communicate with the central server, but not with each other, resulting in star-shaped communication network. At each time step & E [7]. an arbitrary client in E [N] becomes active and chooses an arm X, from a candidate set A, S R4. and then receives the corresponding reward feedback Y/ fx;) + T) R. Note that A, is time-varying, f denotes the unknown reward function shared by all clients, and 77c denotes zero mean sub- aub-Gaussian noise with known variance o².
The performance of the learning system is measured by the cumulative (pseudo) regret over all N clients in the finite time horizon T, i.e., Ri Σi= Tr. where = maxxE, Efylx] E(ys [x, the regret incurred by client it at time step f. Moreover, under the federated learning setting, the system also needs to keep the communication cost Cr low, which is measured by the total number of sealars 44) being transferred across the system up to time T. With the linear reward assumption, i.e., ((x) = x 6., where 0, denotes the unknown parameter, a ridge regression estimator 0, = VV can be constructed based on sufficient statistics from all N clients at each time step t, where V, E X and b, Ei= X.Ys [21]. Using 0, under the Optimism in the Face of Uncertainty (OFUL) principle M1. one can obtain the optimal regret RT = O(v/T). To achieve this regret bound in the federated setting, a naive method is to immediately share statistics of each newly collected data sample to all other clients in the system, which essentially recovers its centralized counterpart. However, this solution incurs a disastrous communication cost Cr- = NTR On the other extreme, if no communication occurs throughout the entire time horizon (i.e., Cr = 0), the regret upper bound can be up to Ry = D(dvNT) when each client interacts with the environment at the same frequency, indicating the importance of timely data/model aggregation in reducing Ry.
To balance this trade-off between regret and communication cost, prior research efforts centered around designing wwammmnicaaion-ffciciiii
protocols for federated bandits that feature the "delayed update" of sufficient statistics 40 22 13 Specifically, each client i only has delayed copy of V, and b. denoted as V ViL.a + A V.. Vi,t by b Abi.,, where V byn is the aggregated
sufficient statistics shared by the server in the last communication, and A AVi,, Abee is the accumulated local updates that client obtain from its interactions with the environment since last In essence, the success of these algorithms lies in the fact that V,, b, typically changes slowly and thus has little instant impact on the regret for most time steps. Therefore, existing protocols that only require occasional communications can still achieve nearly optimal regret, despite the limitation on assuming clients' willingness on participation we discussed before.
3

---

3.2 Incentivized Federated Bandits
Different from the prior works in this line of research, where all clients altruistically share their data with the server whenever a communication round is triggered, we are intrigued in a more realistic setting where clients are self- refffinterested and thus reluctant to share data with the server if not well motivated. Formally, each client in the federated system inherently experiences a cos of data sharing, denoted by Dj E IR, due to their individual consumption of computing resources in local updates or concerns about potential privacy breaches caused by communication with the server. Moreover, the client has nothing to lose when there is no local update to share a communication round at time step t, in this case we assume the cost is O, i.e., D D/ I( # 0). As result, the server needs to motivate clients to participate in data sharing via the incentive mechanism M RV x [Rdxd + RN, which takes as inputs a collection of client local updates AV,, E II dxd and a vector of cost values D2 (Df ... D R and outputs the incentive I {Ii,t... _N,,} E R-V be distributed among the clients. Specifically, to make it possible to measure gains and losses of utility in terms of real-valued incentives (e.g., monetary payment), assumption, as is standard in economic analysis [1].1].
adopt the standard quasi -ineer utility function
At each communication round, a client decides whether to share its local update with the server based on the potential utility gained from participation, i.e. the difference between the incentive and the cost of data sharing. This requires the incentive mechanism to be individually rational:
Definition (Individual Rationality (9) An incentive mechanism M TRN x TRaxd RM
individually rational if for any i in the participant set St at time step t, we have
In 2 D²
(1)
In other words, each participant must be guaranteed non-negative utility by participating in data sharing under M.
The server coordinates with all clients and incentivizes them to participate in the communication to realize its own objective (e.g., collective regret minimization). This requires M to be sufficient:
Definition 2 (Sufficiency) An incentive mechanism M : RN x Raxd - RN is sufficient if the resulting outcome satisfies the server's objective.
Typically, under different application scenarios, the server may have different objectives, such as regret minimization or best arm identification. In this work, we set the objective of the server to minimize the regret across all clients; and ideally the server aims to attain the optimal Odd/T) regret in the centralized setting via the incentivized communication. Therefore, we consider an incentive mechanism is sufficient if it ensures that the resulting accumulated regret is bounded by OddVT).
4 Methodology
The communication backbone of our solution derives from DisLinUCB 40). which is a widely adopted paradigm for federated linear bandits. We adopt their strategy for arm selection and commu- nication trigger, so to focus the incentive mechanism design. We name the resulting algorithm INC-FEDUCB, and present it in Algorithm [ Note that the two incentive mechanisms to be presented in Section 4.2 and 4 are not specific to any federated bandit learning algorithms, and each of them can be easily extended to alternative workarounds as a plug-in to accommodate the incentivized federated learning setting. For clarity, summary of technical notations can be found in Table
4.1 A General Framework: INC-FEDUCB Algorithm
Our framework comprises three main steps: client's local update; 2) communication trigger; and 3) incentivized data exchange among the server and clients. Specifically, after initialization, an active client performs local update in each time step and checks the communication trigger. If communication round is triggered, the system performs incentivized data exchange between clients and the server. Otherwise, no communication is needed.
Note that if the costs are trivially set to zero, then clients have no reason to opt-out of data sharing and our problem essentially reduces the standard federated bandits problem [40).

---

Algorithm INC-FEDUCB Algorithm
Require: D. 2 D (Df Dy o. 0, E (0,1)
1: Initialize: [Server] Vg.0 = Oaxd E Raddd 02.0 0₂ E Rd
2:
AV 1.0 = Odxx: Ab- Og, vj E [N]
3:
[All clients] V4,0 Odxds 6,,0 02. AV,0 = Oaxds Ab Oz. At,, 0, [N]
4: for t = 2......,77 do
5:
[Client i,] Observe arm set A₁
6:
[Client i,] Select arm X₁ E Ar by Eq. 2 and observe reward yt
7:
[Client 4,] Update: V1, += x;X; bi..t + XtI/ AV.. += x;X; Ab..t t += Xiye, Ati.t += det(V det(V,,
8:
9:
if At,,, log det(Vi,, +X77 > De then
10:
[All clients Server] Upload AV,, such that S. Vi [N]}
[Server] Select incentivized participants S. M((s) for ; AV,, E St do
D Incentive Mechanism
12:
Paarticipant Server] Upload Abi, [Server] Update: Vg. += A V.t. by.t += Abi
14:
15:
AV j.t += A Ab-j.t += Ab;,, Vj #i
16:
[Participant i] Update: AV, O, Abi, = 0, Ati, = for vi [N] do
17:
[Server -> All Clients] Download AV i,t, Ab-itt
19:
[Client i] Update: Vi, += AV bi += Ab
[Server] Update: AV-1t Ab_it t
Formally, at each time step i = I,..., .....,T T, an arbitrary client i, becomes active and interacts with its environment using observed arm set Ar (Line 5). Specifically, selects an arm x, A, that maximizes the UCB score as follows (Line 6):
max (i,, + -1,,--1/xxll (A) xEd,
where ( = V- ( is the ridge regression estimator of 0, with regularization parameter À 0, Vi) V and 04, a v log det(V 2 1/0 + vλ. det (A7)
VA,+ denotes the covariance matrix constructed using data available to client in up time f. After obtaining a new data point (x,, y1) from the environment, client checks the communication event dec(Vi, (A))
trigger Ali,t log Ve, dus (A)] > D. (Line 9), where Ali,, denotes the time elapsed since the last time tast it communicated with the server and D. 2 0 denotes the specified threshold.
Incentivized Data Exchange With the above event trigger, communication rounds only occur (1) substantial amount of new data has been accumulated locally client i, and/or (2) significant time has elapsed since the last communication. However, in our incentivized setting, triggering a communication round does not necessarily lead to data exchange at time step the participant set S, may be empty (Line 11). This characterizes the fundamental difference between INC-FEDUCB and DisLinUCB [40]: we no longer assume all N clients will share their data with the server in an altruistic manner; instead, a rational client only shares its local update with the server if the condition in Eq. (I) is met. In light of this, to evaluate the potential benefit of data sharing, all clients must first reveal the value of their data to the server before the server determines the incentive. Hence, after communication round is triggered, all clients upload their latest sufficient statistics update AV,, to the server (Line 10) to facilitate data valuation and participant selection in the incentive mechanism (Line 11). . Note that this disclosure does not compromise clients' privacy, as the clients' secret lies in Abi. that is constructed by the rewards. Only participating clients will upload their Abú, the server (Line 13). After collecting data from all participants, the server downloads the aggregated updates AV-1, and Ab-i, every client (Line 17-20). Following the convention in federated bandit lcarning [40], the communication cost is defined as the total number of scalars transferred during this data exchange process.
5

---

Algorithm 2 Payment-free Incentive Mechanism
Require: D = (D [N]]. S, = & [N])
Initialize participant set 5² St
2: while St * 8 do
> iteratively update St until it becomes stable
3: StableFlag True
4: for i: A V. E St do
5: if Ii, < D then
Eq.
6:
Update participant set S; = St {
b. remove client j from S
7:
StableFlag False
8:
break
9: if StablcFlag True then break
10:
11:
return St St
4.2 Payment-free Incentive Mechanism
As mentioned in Section 1 in federated bandit learning, clients can reduce their regret by using models constructed via shared data. Denote V the covariance matrix constructed by all available data in the system at time step t. Based on Lemma and 7 the instantaneous regret of client i, is upper bounded by:
det((V-1) rs < 20 x 1x V det((V..-1))
= (Vars 7 ||x||| V
det (Ve-)) det(VV.,--1)
(3)
where the determinant ratio reflects the additional regret due the delayed synchronization between client de's 's local sufficient statistics and the global optimal oracle. Therefore, minimizing this ratio directly corresponds to reducing client i regret. For example, full communication keeps the ratio at 1, which recovers the regret of the centralized setting discussed in Section 3.1
Therefore, given the client's desire for regret minimization, the data itself can be used as form of incentive by the server. And the star-shaped communication network also gives the server an information advantage over any single client in the system: client can only communicate with the server, while the server can communicate with every client. Therefore, the server should utilize this advantage to create incentives (i.e., the LHS of Eq. ([)) and natural design to evaluate this data incentive is:
del (Di,r(t)) + Va..) dct((V..)
I T
where
AVj, + AV-,a denotes the data that the server can offer to client during the communication at time (i.e., current local updates from other participants that have not been shared with the server) and A AV-i,t is the historically aggregated updates stored in the server that has not been shared with client i. Eq. (4) suggests substantial increase in the determinant of the client's 's local data is desired by the client, which ultimately results in regret reduction.
With the above data valuation in Eq. (4), propose the payment-free incentive mechanism that motivates clients to share data by redistributing data collected from participating clients. We present this mechanism in Algorithm 2 and briefly sketch it below. First, we initiate the participant set S, = S,, assuming all clients agree to participate. Then, the willingness of each client in S, according to Eq. ( S, is empty or clients in are participating, then terminate; otherwise, remove client from S, and repeat the process.
iteratively update S, by checking
While this payment-free incentive mechanism is neat and intuitive, it has guarantee the amount of data that can be collected. To see this, we provide theoretical negative result with rigorous regret analysis in Theorem 3 (see proof in Appendix C,
Theorem (Sub-optimal Regret) When there are most ZC log(T/N) number of clients (for some
N
Ad )d), there exists linear bandit instance with = L S = 1 such that for T Z Nd, the expected regret for INC-FEDUCB algorithm with payment-free incentive mechanism is at least (Td
constant C, c > 0), whose cost value DÒ I min (1+ (1)+2)T (1+ TL²

---

Algorithm 3 Payment-efficient Incentive Mechanism
Require: S, , ]. data-incentivized participant set S, C S, threshold /
for client AV,, E Se \ S. do:
2: Compute client's s potential contribution to the server (i.e., marginal gain in determinant):
ci,r(S: det(AVi,
(g,)(S;) - 27()))
(6)
3: Rank clients {i...... im) } by their potential contribution, where m = =|, Se1
4: Segment the list by finding a - min(j] des(V (S)(V.. 2 3, Vj E [m]]
det(Vn..(S.)
5: k = a - I, D. - IVd
6: return participant set S, = Heuristic Search(k; (m)))
> Algorithm
Recall the discussion in Section 3.1 when there is no communication Rr is upper bounded by Odd/NT). Hence, in the worst-case scenario, the payment-free incentive mechanism might not motivate any client to participate. It is thus not a sufficient mechanism.
4.3 Payment--fficient Incentive Mechanism
To address the insufficiency issue, we further devise a payment-efficien incentive mechanism that introduces additional monetary incentives to motivate clients' participation:
Ii, I Z
(5)
where 7 is the data incentive defined in Eq. 4 and Z is the real-valued monetary incentive, i.e., the payment assigned to the client for its participation. Specifically, we intrigued by the question: rather than trivially paying unlimited amounts to ensure everyone's participation, can we devise an incentive mechanism that guarantees certain level of client participation such that the overall regret is still nearly optimal but under acceptable monetary incentive cost?
Inspired by the determinant ratio principle discussed in Eq. (3), we propose to control the overall regret by ensuring that every client closely approximates the oracle after each communication round, which can be formalized as (V,,V) (V.) 2 B, where Vg. = V with all clients and (S.)) = Ej.av,, AVj.- The parameter 8 E [0, 1] characterizes the chosen gap between the practical and optimal regrets that the server commits to. Denote the set of clients motivated by I at time as Sy and those motivated by I S.m and thus St S Sy At each communication round, the server needs find the minimum Zn such that pooling local updates from S, satisfies the required regret reduction for the entire system.
E(S)) to shared
Note that Algorithm 2 maximizes Z and thus the servers should compute Z on top of optimal I and resulting Sy which however still combinatorially hard. First, a brute-force search can yield a time complexity up to O(2*). Second, different from typical optimal subset selection problems [17, the dynamic interplay among clients in our specific context brings unique challenge: once client incentivized share data. the other uninvolved clients may change their willingness due the increased data incentive, making the problem even more intricate.
To solve the above problem, propose heuristic ranking- based method, outlined in Algorithm 3 The heuristic is to rank clients by the marginal gain they bring to the server's determinant, as formally defined in Eq. (6), which helps minimize the number of clients requiring monetary incentives, while empowering the participation of other clients motivated by the aggregated data. This forms an iterative search process: First, we rank all m non non-participating clients (Line 2-3) by their potential contribution to the server (with participant set S, committed); Then, we segment the list by 8, anyone whose participation satisfies the overall 3 gap constraint is an immediately valid choice (Line 4). The first client i, in the valid list and its payment I (oo if not available) will be last resort (Line 5); Lastly, we check if there exist potentially more favorable solutions from the invalid list (Line 6). Specifically,
-1 (k list in n & rounds, where only one client will be chosen using the same heuristic in each round. If having clients from the invalid list also satisfies the 3 constraint and results in a reduced monetary
try to elicit up A
if i is not available) clients from the invalid
7

---

incentive cost compared to T then we opt for this alternative solution. Otherwise, we will adhere the last resort.
This Heuristic Search detailed in Appendix A and demonstrates time complexity of only O(N) in the worst-case scenarios, i.e., = = N. Theorem guarantees the sufficiency of this mechanism Wel communication and payment bounds.
Theorem Under threshold 3 and clients' committed data sharing cost D = (D9, ... D2 with high probability the monetary incentive cost of UNC-FEDUCB satisfies
MT = 00
max max P -
N Σ P. 1=1
(..((dec (del(AT) F
(dtt(Vr))
where P, is the number of epochs client i gets puid throughout time horizon T, P is the total number of epochs, which is bounded P O( log T) by setting communication threshold D, =
N=dlog NedRlogT log 3, where R = [d + 12)1
T2
Henceforth, the communication cost satisfies
CT O(Nd)) P (og
Furthermore, by setting B 2 e ,,, the cumulative regret is
PT 00 0d
The proof of theorem can be found in Appendix
5 Experiments
We simulate the incentivized federated bandit problem under various environment settings. Specifi- cally, create enviromment of N 50 clients with cost of data sharing DP .... total number of iterations T = 5, 000, feature dimension d = 25, and time-varing arm pool size K = 25. By default, we set D D E IR, vi E [N]. Due to the space limit, more detailed results and discussions on real-world dataset can be found in Appendix
32
1.99
630
1160
1091
2200
10.03
10:00
1030
(a) DP
(b) DE
10
(c) D2
100
Figure 1: Comparison between payment-free vs. payment-efffcient incentive designs. The results averaged over 10 runs with standard deviation as the error bars.
5.1 Payment-free vs. Payment-efficient
We first empirically compared the performance of the payment-free mechanism (named as INC- FEDUCB-PF) and the payment-efficient mechanism INC-FEDUCB in Figure [ It is clear that the added monetary incentives lead lower regret and communication costs, particularly with increased D Lower regret is expected as more data can be collected and shared; while the reduced communication cost is contributed by reduced communication frequency. When less clients can be motivated in one communication round, more communication rounds will be triggered as the clients tend to have outdated local statistics.

---

In- infeedcC rnc
135
1.
1204
2
25
2462
00:02
05
1-18
Accumulative Regret
(b) Communication Cost
(c) Payment Cost
Figure 2: Ablation study on heuristic search (w.r.t D E [1, 100). The results are averaged over 10 runs with standard deviation as the error bars.
5.2 Ablation Study on Heuristic Search
To investigate the impact of different components in our heuristic search, we compare the full-fledged model INC-FEDUCB with following variants on various environments: (1) INC-FEDUCB (w/o PF); without payment-free incentive mechanism, where the server only use money to incentivize clients; (2) INC-FEDUCB (w/o IS); without iterative search, where the server only rank the clients once. (3)
INC-FEDUCB (w/ PF + IS): without both above strategies.
present the averaged learning trajectories of regret and communication cost, along with the final payment costs (normalized) under different D The results indicate that the full-fledged INC-FED INC-FEDUCB consistently outperforms all other variants in various environments. Additionally, there is a substantial gap between the variants with and without the strategy, emphasizing the significance of leveraging the server's 's information advantage to motivate participation.
In Figure 2
5.3 Environment & Hyper-Parameter Study
We further explored diverse 3 hyper-paramette settings for INC-FEDUCB in various environments with varying D along with the comparison with DisLinUCB (40] (only comparable when D = 0). Specifically, explored different hyper-parametee settings for INC-FEDUCB with determinant ratio threshold E [0.3, 0.7, and various environmental configurations with data sharing cost DP 10, 100].
25,
DisLiaUCB
INC-FEDUCB (#
IXC-FEDUCB (3 0.7)
INC-FEDUCB (# 0.3)
Regret (Acc.)
48.46
48.46
48.46 (A 0%)
48.46 (A 0%)
5,000, DE
Commu. Cost
7,605,000
7.605.000
7,605,000 0%)
7,605,000 0%)
Pay.
0 0%)
0%)
Regret (Acc.)
(A.
(A. 0.2%)
= 5,00, N- 50,
Commu. Cost
7,605.000
7,668,825 (2. 0.8%)
7.733.575 (.) 1.7%)
Pay. Cost
75.12
60.94 (3 18.9%)
22.34 70.9%)
Repret (Ace.)
48.46
48.21 (A 0.5%)
47.55 (A. 1.9%)
T- 5,000, 50,
7.605
7.779,425 (A. 2.3%)
Pay. Cost
12,819.61
9,050.61 (A 29.4%)
4,859.17 (.. 62.1%
Regret (Acc.)
48.46
48.22 (A. 0.5%6)
48.44 (A. 0.1%)
7-5,000,8 DE
Commu, Cost
7.605 ,000
7,842,775 (2. + 3.1%)
8.718.425
14.6%)
Pay.
190,882.45
(A. -..1%%
53.455
Table 1: Study hyper-parameter of INC-FRDUCB and environment.
As shown in Table when all clients are incentivized to share data, our INC-FED essentially recover the performance of DisLinUCB, while overcoming its limitation in incentivized settings when clients are not willing to share by default. Moreover, by reducing the threshold B, we can substantially save payment costs while still maintaining highly competitive regret, albeit at the expense of increased communication costs. And the reason for this increased communication cost has been explained before: more communication rounds will be triggered, clients become more outdated.

---

6 Conclusion
In this work, we introduce a novel incentivized communication problem for federated bandits, where the server must incentivize clients for data sharing. We propose general solution framework INC-FEDUCB, and initiate two specific implementations introducing data and monetary incentives, under the linear contextual bandit setting. We prove that INC-FEDUCB flexibly achieves customized levels of near-optimal regret with theoretical guarantees on communication and payment costs. Extensive empirical studies further confirmed our versatile designs in incentive search across diverse environments. Currently, assume all clients truthfully reveal their costs of data sharing the server. We are intrigued in extending our solution to settings where clients can exhibit strategic behaviors, such misreporting their intrinsic costs of data sharing to increase their own urility. is then necessary to study a truthful incentive mechanism design.
Acknowledgement. We thank the anonymous reviewers for their insightful and constructive com- ments. This project is partially supported by NSF Award IIS-2213700 and IIS-2128019. Haifeng Xu supported by an NSF Award CCF-2303372, an Army Research Office Award -NN--3--1--0001 and an Office of Naval Research Award N00014-23-1-2802.
References
[1] Yasin Yadkor, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. NIPS, volume 11, pages 2312-2320, 2011.
[2] Maurice Allais. Le comportement de I'homme rationnel devant le risque: critique des postulats et axiomes de I' l'école américaine. Econometrica: Journal of the econometric society, pages 503-546, 1953.
[3] Nicolo Cesa-Biance Claudio Gentile, and Giovanni Zappella. A gang of bandits, In Advances in Neural Information Processing Systems, pages 737-745, 2013.
[4] Mithun Chakraborty, Kai Yee Phoebe Chua, Sanmay Das, and Brendan Juba. Coordinated versus decentralized exploration in multi-agent multi-armed bandits. In IJCAI, pages 164-170, 2017.
[5] Yae Jee Cho, Divyansh Jhunjhunwala, Tian Li, Virginia Smith, and Gauri Joshi. To federate or not to federate: Incentivizing client participation in federated learning. In Workshop on Federated Learning: Recent Advances and New Challenges (in Conjunction with NeurIPS 2022), 2022.
[6] Jiu Ding and Aihui Zhou. Eigenvalues of rank-one updated matrices with some applications. Applied Mathematics Letters, 20(12):1223-133 2007.
[7] Kate Donahue and Jon Kleinberg. Model-sharing games: Analyzing federated learning under voluntary participation. In Proceedings of the AAAI Conference Artificial Intelligence, pages 5303-5311, 2021.
[8] Kate Donahue and Jon Kleinberg. Fairness in model sodell-haring games. In Proceedings of the ACM Web Conference 2023, pages
2023.
[9] Yihan Du, Wei Chen, Yuko Kuroki, and Longbo Huang. Collaborative pure exploration in kernel bandit. In The Eleventh International Conference Learning Representations, 2023.
[10] Abhimanyu Dubey and AlexSandy' Pentland. Differentially-priiate federated linear bandits. Advances in Neural Information Processing Systems, 33:6003-6014 2020.
[11] Sarah Filippi, Olivier Cappe, Aurélien Garivier, and Csaba Szepesvári. Parametric bandits: The generalized linear case. Advances in Neural Information Processing Systems, 23, 2010.
[12] F Maxwell Harper and Joseph Konstan. The movielens datasets: History and context, Acm transactions interactive intelligent systems (tiis, 5(4):1-19, 2015.
10

---

[13] Jiafan He, Tianhao Wang. Yifei Min, and Quanquan Gu. A simple and provably efficient algorithm for asynchronous federated contextual linear bandits. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Process- ing Systems, volume 35, pages 4762-4775. Curran Associates, Inc., 2022.
[14] Rui Hu and Yanmin Gong. Trading data for learning: Incentive mechanism for on-device federated learning. In GLOBECOM 2020-2020 IEEE Global Communications Conference, pages 1-6. IEEE, 2020.
[15] Ruiquan Huang, Weiqiang Wu, Jing Yang, and Cong Shen. Federated linear contextual bandits. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 27057-27068. Curran Associates, Inc., 2021.
[16] Sai Praneeth Karimireddy, Wenshuo Guo, and Michael Jordan. Mechanisms that incentivize data sharing in federated learning. In Workshop on Federated Learning: Recent Advances and New Challenges (in Conjunction with NeurIPS 2022), 2022.
[17] Ron Kohavi and George H John. Wrappers for feature subset selection. Artificial intelligence, 97(1-2):273-322 1997.
[18] Nathan Korda, Balazs Szorenyi, and Shuai Li. Distributed clustering of linear bandits in peer to peer networks. In International conference on machine learning. pages 1301-1309, PMLR. 2016.
[19] Peter Landgren, Vaibhav Srivastava, and Naomi Ehrich Leonard. On distributed cooperative decision-maie makinn in multiarmed bandits. In 2016 European Control Conference (ECC), pages 243-248, IEEE, 2016.
[20] Peter Landgren, Vaibhav Srivastava, and Naomi Ehrich Leonard. Social imitation in cooperative multiarmed bandits: Partition-based algorithms with strictly local information. In 2018 IEEE Conference Decision and Control (CDC), pages 5239-5244. IEEE, 2018.
[21] Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[22] Chuanhao Li and Hongning Wang. Asynchronous upper confidence bound algorithms for federated linear bandits. In International Conference on Artificial Intelligence and Statistics, pages 6529-6553. PMLR, 2022.
[23] Chuanhao and Hongning Wang. Communication efficient federated learning for generalized linear bandits. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022.
[24] Chuanhao Li, Huazheng Wang, Mengdi Wang, and Hongning Wang- Communication efficient distributed learning for kernelized contextual bandits. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances Neural Information Processing Systems, 2022.
[25] Chuanhao Li, Huazheng Wang, Mengdi Wang, and Hongning Wang. Learning kernelized contextual bandits in a distributed and asynchronous environment. The Eleventh International Conference on Learning Representations, 2023.
[26] Lihong Li. Wei Chu, John Langford, and Robert E Schapire. A contextual- approach to personalized news article recommendation. In Proceedings of the 19th international conference on World wide web, pages 661-670, 2010.
[27] Keqin Liu and Qing Zhao. Distributed learning in multi-armed bandit with multiple players. IEEE transactions on signal processing,
2010.
[28] David Martínez-Rubio, Varun Kanade, and Patrick Rebeschini. Decentralized cooperative stochastic bandits. Advances Neural Information Processing Systems, 32, 2019.
[29] Roger B Myerson and Mark Satterthwaite. Efficient mechanisms for bilateral trading. Journal of economic theory, 29(2)265--88,, 1983.

---

[30] Jian Pei. A survey on data pricing: from economics to data science. IEEE Transactions on knowledge and Data Engineering. 34(10):4586 4608, 2020.
[31] Malcolm Pemberton and Nicholas Rau. Mathematics for economists: an introductory textbook. Manchester University Press, 2007.
[32] Abishek Sankararaman, Ayalvadi Ganesh, and Sanjay Shakkottai. Social learning in multi agent multi armed bandits. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 3-3), 2019.
[33] Chengshuai Shi, Cong Shen, and Jing Yang. Federated multi-armed bandits with personalization. In International Conference on Artificial Intelligence and Statistics, pages 2917-2925. PMLR, 2021.
[34] Chengshuai Shi, Wei Xiong, Cong Shen, and Jing Yang. Decentralized multi-player multi-armed bandits with collision information. In International Conference Artificial Intelligence and Statistics, pages 1528.. PMLR, 2020.
[35] Rachael Hwee Ling Sim, Yehong Zhang, Mun Choon Chan, and Bryan Kian Hsiang Low. Collaborative machine learning with incentive-aware model rewards. In International conference on machine learning, pages 8927-8936. PMLR, 2020.
[36] Balazs Szorenyi, Róbert Busa-Fekete, István Hegedus, Róbert Ormándi, Márk Jelasity, and Balázs Kégl. Gossip-based distributed stochastic bandit algorithms. In International conference on machine learning, pages 19-27. PMLR, 2013.
[37] Chao Tao, Qin Zhang, and Yuan Zhou Collaborative learning with limited interaction: Tight bounds for distributed exploration in multi-armed bandits. In 2019 JEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 126-146. IEFE, 2019.
[38] Xuezhen Tu, Kun Zhu, Nguyen Cong Luong, Dusit Niyato, Yang Zhang, and Juan Li. Incentive mechanisms for federated learning: From economic and game theoretic perspective. IEEE Transactions on Cognitive Communications and Networking. 2022.
[39] Po-An Wang, Alexandre Proutiere, Kaito Ariu, Yassir Jedra, and Alessio Russo. Optimal algorithms for multiplayer multi-armed bandits. In International Conference on Artificial Intelligence and Statistics, pages 4120-4129. PMLR, 2020.
[40] Yuanhao Wang. Jiachen Hu, Xiaoyu Chen, and Liwei Wang. Distributed bandit learning: Near-optimal regret with efficient communication. In International Conference on Learning Representations, 2020.
[41] Xinyi Xu, Lingjuan Lyu, Xingjun Ma. Chenglin Miao, Chuan Sheng Foo, and Bryan Kian Hsiang Low. Gradient driven rewards to guarantee fairness in collaborative machine learning. Advances in Neural Information Processing Systems, 34: 16144-10111 2021.
[42] Yufeng Zhan, Jie Zhang, Zicong Hong. Leijie Wu, Peng Li, and Song Guo. A survey of incentive mechanism design for federated learning. IEEE Transactions on Emerging Topics in Computing, 103)):033-10044 2021.
[43] Zhaowei Zhu, Jingxuan Zhu, Ji Liu, and Yang Liu. Federated bandit: A gossiping approach. In Abstract Proceedings of the 2021 ACM SIGMETRICS/neematione Conference on Measurement and Modeling of Computer Systems, pages 3-4, 2021.
12

---

A Heuristic Search Algorithm
Algorithm 4 Heuristic Search
Require: invalid client list { .., dx iataainnentivized participant set S., and the last resort cost Tlast
1: Initialization: S.
2: for E [k] do
3: Rank clients fi1....,.k i (in new order) by Eq (6)
4: St S S, U (ik-n+1)
> add the client with the largest contribution
5: for client j E (i1..... i
> find extra data-incentivized participants
6:
Compute data incentive T for client j by Eq
7:
if I > DJ then S: = S.
8:
9:
Compute total payment IHe EiEsnr. I.t by Eq 55)
if IW I Taast then
11:
return St S.=S.U =S.UAAV...
return last resort
12: else
13:
det(E((.) if (((e)EE(S)))))) + (gttii)det((E(S)) + Vo.t-1)> B then
return
D return search result
As sketched in Section 4.3 we devised an iterative search method based on the following ranking heuristic (formally defined in Eq. (6)): the more client assists in increasing the server's determi- nant, the more valuable its contribution is, and thus we should motivate the most valuable clients to participate. Denote & (initializedd 1) the number of clients be selected from the invalid
list fi...... }. and initialize the participant set S. St. In each round n. we rank the remaining - n + clients based on their potential contribution to the server by Eq. (6). and add the most valuable one S, (Line 3-4). With the latest S, committed,
then proceed to determine additional data-incentivized participants by Eq. (4) (Line 5-8), and compute the total payment by Eq. (5) (Line 9). If having clients results in the total cost I,!,: > I then terminate the search and resort to our last resort (Line 10-11). Otherwise, if the resulting S; enables the server to satisfy the 3 gap requirement, then we successfully find a better solution than last resort and can terminate the search. However, if having n client is insufficient for the server to pass the 3 gap requirement, we increase n + 1 and repeat the search process (Line 12-14). partieular, if the above process fails to terminate (i.e., having all m clients still not suffices, we will still use the last resort. Note that, by utilizing matrix computation to calculate the contribution list in each round, this method only incurs a linear time complexity of (NN,, when n m N.
B
Technical Lemmas
Lemma 5 (Lemma H.3 of [40)) With probability 1 1- 5, single step psendo-regret 10" x0= -x.) bounded by
T + +21/2) ||x, |Ixellyz7 = =0 ( |xellvz,
(22lgg
rt 2
5
Lemma 6 (Lemma 11 of (1) Let ( be sequence in Idd, V is a positive definite matrix and define V, V E X.X.. Then we have that
det (Vn) dct(VV)
log
1x 12
t=1
Further, if X S L for all then
min { 1, [eel }
< (log det (V.) - log V) 5 ldg ((trace(V) + nbb) /d) log det V)
13

---

Lemma 7 (Lemma 12 of (1)
Let A, B and C' be positive semi semi-definite matrices such that A
B + C. Then, we have that
x
Ax
det(A)
sup x x
Bx
det
C Proof of Theorem 3
Our proof relies the following lower bound result for federated linear bandits established in 13
Lemma 8 (Theorem 5.3 of (3) Let pi denote the probability that agent E [N] will communi- cate with the server at least once over time horizon T. Then for any algorithm with
N
N
2C
(T/()/N)
there always exists linear bandit instance with o L = S 1, such that for T 2 Nd, the expected regret of this algorithm is at least NT)
In the following, we will create a situation, where Eq. 77) always holds true for the payment-free incentive mechanism. Specifically, recall that the payment-free incentive mechanism (Section 4.2) motivates clients to participate using only data, i.e., the determinant ratio defined in Eq. 4 that indicates how much client i's confidence ellipsoid
shrink using the data offered by the server.
Based on matrix determinant lemma G6, we know that I,, S (1 + X )². Additionally, by applying the determinant trace inequality (Lemmaa 10 of [I), have I,, S + TL Ad Therefore, long
as D. >> min((1 + L),, (1+ T2² where the tighter choice between the two upper bounds depends the specific problem instance (i.e., either d or being larger), becomes impossible for the server to incentivize client to participate in the communication. Now based on Lemma
Ad
the number of clients that satisfy DP I min((1+ 4),, (1 )d is smaller than 20 (Tg()
sub-optimal regret of the order M(dvNT) is inevitable for payment-fire incentive mechanism. which finishes the proof.
D Proof of Theorem
To prove this theorem, we first need the following lemma.
Lemma (Communication Frequency Bound) By setting the communication threshold De =
d T V N- log 3, the total number of epochs defined by the communication rounds satisfies,
P = O(NdlogT)
where R = [dlog(1 Ta] = Old 7).
Proof of Lemma g Denote P as the total number of epochs divided by communication rounds throughout the time horizon T, and Vg,4, as the aggregated covariance matrix at the p-th epoch. Specifically, Vg.t, AI, Vi is the covariance matrix constructed by all data points available in the system at time step T.
Note that according to the incentivized communication scheme in INC-FEDUCB, not all clients will necessarily share their data in the last epoch, hence det (V,,,)) S det((Vr) < (r(( < (A+T/d)d Therefore,
det (Vg,t))))) + log det(Vg.tr-1) + + log det((V.tt) log log det
det((g,tt) det(Vy.to) < doog(1 + Xd
)
det(V det(Vg.tr_a)
det(V g.t.)
Let a R+ an arbitrary positive value, for epochs with length greater than a, there are at most [ of them. For epochs with length less than a, say the p-th epoch triggered by client i, we have
M4s log det(Vv.)))
> De
dct((V.tne)
14

---

Combining the 3 gap constraint defined in Section 4.3 and the fact that the server always downloads all clients at every communication round, we have Sti,t, S and hence
log det(g, Vip) log B -d,e log B. det del 1) del(V 1)
De log B det(Vess)) del(V,,tuue
+ +og B
de.((V,,,-1))
a
Let R = [doog(1 + x Oddoog 7), therefore, there are at most
epochs with length
+log
less than a time steps. As result, the total number of epochs P S
+
R
Note that
Da Hog
R
2 2
TR D. log where the equality holds when a Do
De +log
B
Furthermore, let De
T Nadlng a log 3, then
T2 NadRlog T we have
P=O
(v
TR De + log
O(N ((NVdRllgT) = O(N
(8)
This concludes the proof of Lemma 9
The proof of communication cost upper bound directly follows Lemma In each epoch, all clients first upload O scalars to the server and then download (dd) scalars. Therefore, the total communication cost is Cr = P- O(Nd)) O(N2d log T))
Communication Cost:
Monetary Incentive Cost: Under the clients' committed data sharing cost DP DD..... D during each communication round at time step lp, we only pay clients in the participant set S... Specifically, the payment (i.e., monetary incentive cost) Li O if the data incentive is already sufficient to motivate the client to participate, i.e., when Idd 1.1p 2 D.P Otherwise, we only need to pay the minimum amount of monetary incentive such that Eq. is satisfied, i.e., Ihtp D. T Therefore, the accumulative monetary incentive cost is
N
N
max f0, DP I } I(AV, E St,))
Mr
1 1=1
0, 1max((? 3- I } I(AVis, E Stp)
max
(E(N)
p=1
(max (D.) I MAVI, S.,))) kE(N
p= NeN
P N
P AAVi, E Et.)))
$ max KE[M
max
(D,}}
Σ p=li=1
- I.,, IV,, 1(Vi, E St
IEN,
P
N
max [D,) EE[N]
Σ N - Σ3 I
t=1 PEP:
where P and N represent the number of epochs and clients, N, is the number of participants in p-th epoch, Nr, is the set of noney-incentivized participants in the p-th epoch, P, is the set of epochs where client gets monetary incentive, whose size is denoted P. = [P.). Denote Dr max { to simplify our later discussion.
Recall the definition of data incentive and Dis,, ( introduced in Eq. 4
ESSAV AVi,, + AV
show that
det (Di.,, (S,,,) + Vetg))
del (Vi,,,
dct(VVite)
>
dct(Vi..p)
15

---

Therefore, we have
N
NV
det( V vg
Mr S
D
max
Σ
N2
det(V1,
1m1
pEP,
PEP:
D
N
N
P
Pi
det((Vg.t) del(Vin))
guts
det((a..t))
det(Vg.to))
max
det(Vi,t))
del del
1=1
i=1
P
N
N
det(Vi,t) det((g
det(Viiep.-) det(Vien) (Vier
44.
S DP
No
+
Σ
P.
Σ
Pr
max
det(Vis.))
det(Viaa)
p=1
1=1
i=1
N
* deet(Vg.t))
DP
max
Σ Nr
Σ P;
Σ
P;
det(Vi,e)))
1=1
i=1
(det(2)) det(Vr)
A
$ (1 D D P.N.
Σ P.
1=1
where the second step holds by Cauchy-Schward inequality and the last step follows the facts that P. S P. Nr & N, de Z det(A/), and det(Vi.) S der()
Specifically, by setting the communication threshold D. N' R [o + 7. we have the total number of epochs P= O(Ndlog T) (Lemma
log 8, where
N'aR log
Therefore,
(de((A)) ddt((TT)
#
MT S (1 D ONN
Σ P.
=ONN2
which finishes the proof.
Regret: To prove the regret upper bound, we first need the following lemma.
Lemma (Instantaneous Regret Bound) Under threshold B, with probability 1 8, the instan- taneous pseudo-regret Ti (0",x' -x)) in j-th epoch is bounded by
rt = ( (valos) T) 7) |
det(Vg,e,) det(Vg.e,..)
V
Proof of Lemmal
10 Denote VÚ as the covariance matrix constructed by available data in the system at time step I. As introduced in Eq. (3). the instantaneous regret of client i is upper bounded by
det((V-1) = =0 Vdloo Tt S 20 x V V det(VV,,)-))
T
det det(V.,,e-1)
||xe ||x|||i
V
Suppose the client i appears at the j-th epoch, i.e., fリ-1 S1St lj. As the server always downloads the aggregated data every client each communication round, we have
det(Vi) det (Vi,.)
det((V))
det(Vi)
det(Vi,, det(V
Combining the gap constraint defined in Section
4.3
we can show that
del (V) dei dct(Vv.e;..)
det( det(Vg,t,)/3
del(Vo.t))
det (V.,.)
det(VV,t5-))
F det
Lastly, plugging the above inequality into Eq.
33 we have
= ( ||xlllizi V
7)
det(Vg.t,)
det(Vy.e,-.)
16

---

which finishes the proof of Lemmal
10
Now, ready to prove the accumulative regret upper bound. Similar to DisLinUCB [40] group the communication epochs into good epochs and bad epochs.
dot(Va.e)) dei(Va.tg_1)
Good Epochs: Note that for good epochs, have Lemma T0 the instantaneous regret in good epochs is
S 2. Therefore, based
Tr (v
T dlog 5
2 V
Denote the accumulative regret among all good epochs REG goods then using the Cauchy-Schward inequality we can see that
RFG good
Σ
pE P iE
ri
PEP ggod BEBp
T T do g
$
Σ
x 11 13--1
PEPpoud goud EEB
Combining the fact x < 2 log(1 + x), Ve E [0, and Lemma 6 we have
T Σ Σ210g
REG good SO
log T
1+ ||X| V=
Pe yoood EEB,
log det dcs
0
log
det((V,..))
Pe P pood
log (V,)),
0
T
log
dVe(VV
PE PAR
d
T
log dee((ee))
T
log
B
8
det(Vie)
d
T
T Ad
00
T
log
dlog
1
5
T
=
VT
V
log
logT
VB
Bad Epochs: Now moving on to the bad epoch. For any bad epoch starting from time step f, to time step te, the regret in this epoch is
N 1
REG
Σ t=t.
Tr 1=1 TEM
where Mi(t) = {1 <T<ti = i} denotes the set of time steps when client interacts with the environment up Combining the fact r, and Lemma [ we have
T (Vallog
rf < min 20,,. -1 -- x_ V--! x
min(1, 1, [111|I//xllva ||x=|ly=1_
8
17

---

Therefore,
REGSO
[Vdlog T
E
min X- |x
i=1 TEN((t)WWi.)))
0o
T
1og
Alix (EA
min Xx 1
8
0
dlog
Ati Σ
log
|+ 1 ||+ 1|
(eNi(t))Wa(tt))
(V dog
log del(Vi,))
Alite
Σ
det(Vi,--1)
FENi(t)WW(tt))
Ate. log dot(Vi.e)
[V dlog
det (Vi
0
dlog
N De.
where the second step holds by the Sauchy-Schward inequality, the third step follows from æ S 2 log(1 + z), Vz E [0, 1], the fourth step utilizes the elementary algebra, and the last two steps follow the fact that no client triggers the communication before t..
Recall that, as introduced in Lemma 9. the number of bad epochs is less than R = [dlog(1 + F) Old I",, therefore the regret across all bad epochs is
REGbad -
T (V Valos z
N D. Oldlog
=0 -0(Na'a
Nd v De log J log
T De-oog
Combining the regret for all good and bad epochs, we have accumulative regret
Rr = RFG good + REGbad
=o ( vB
log llg T +0 (NNLS,
Dr log log
According to Lemma 10 the above regret bound holds with high probability 1- 8. For completeness, we also present the regret when it fails to hold, which is bounded by 8 "rr s 2T 5 in expectation. And this can be trivially set O(1) by selecting analyzing the following regret when the bound holds.
1/T. In this way. we can primarily focus on
( VB
Rr 0
T VT log + (Nal.5 log logi.5 T / DD))
With our choice of D. Nodlog
Nedilogg
T2
log 3 in Lemma
we have
Ry =0 (1
d V (lggr) +0 1og T.
T
T2 log 3
W2dRloggs
Plugging in R [llog(1 11) Od T), we get
PT = 0 ( d VTlogg + + NN [Nd_=log log 15.
T
T
1
log
N2d
Nd T
18

---

D. R. Vi [N]. Furthermore, by setting B > e- & we can show that Nzdlog
2'
T
log 3. and therefore
Ndlog
Ry = 0 ( VTlggT + + o = =0 -
This concludes the proof.
E Detailed Experimental Results
In addition to the empirical studies on the synthetic datasets reported in Section 5 we also conduct
comprehensive experiments on the real-world recommendation dataset MovieLens [2]. Following [ [2 we pre-processed the dataset to align it with the linear bandit problem setting, with feature dimension = 25 and arm set size (movies). where items receiving non-zerr zero ratings are considered as having positive feedback, i.c., denoted by reward of I; otherwise, the reward is O. In total, there are T 214729 interactions, with each user having at least 3000 observations. By default, we set all clients' costs of data sharing D.
25. Specifically, contains N 54 users and 26567 items
E.1 Payment-free Payment-efficien incentive mechanism (Supplement to Section 5.1
Bandic
(a)
D
(b) D. 10
(c) D. 100
Figure 3: Comparison between payment-free vs. payment-efficient incentive designs.
Aligned with the findings presented in Section 5.1 the results real-world dataset also confirm the advantage of the payment-efficient mechanism over the payment-free incentive mechanism in terms of both accumulative (normalized) reward and communication cost. As illustrated in Figure 3 this performance advantage is particularly notable in a more conservative environment, where clients have higher D.. And when the cost of data sharing for clients is relatively low, the performance gap between the two mechanisms becomes less significant. We attribute this to the fact that clients with low DP values are more readily motivated by the data alone, thus alleviating the need for additional monetary incentive. On the other hand, higher values of D. indicate that clients are more reluctant to share their data. As a result, the payment- free incentive mechanism fails to motivate sufficient number of clients to participate data sharing, leading to noticeable performance gap, as evidenced in Figure 3(c) Note that the communication cost exhibits a sharp increase towards the end of the interactions. This is because the presence of highly skewed user distribution in the real- world dataset. For instance, in the last 2,032 rounds, only one client remains actively engaged with the environment, rapidly accumulating sufficient amounts of local updates, thus resulting in increase in both communication frequency and cost.
E.2 Ablation Study on Heuristic Search (Supplement Section 5.2
We further study the effectiveness of each component in the heuristic search of INC-FED on the real-world dataset and compare the performance among different variants across different data sharing the variants without payment-free (PF) component, which
costs. As presented in [igure/4[a]andddpp only rely monetary incentive motivate clients participate, generally exhibit lower rewards and higher communication costs. The reason is a bit subtle: as the payment efficient mechanism is subject to both 3 gap constraint and minimum payment cost requirement, it tends to satisfy the gap constraint with minimum amount of data collected. But the payment free mechanism will always collect the maximum amount data possible. As result, without the PF component, the server
19

---

287
(a) Normalized Reward
(b) Communication Cost
(c) Payment Cost
Figure 4: Ablation study on heuristic search (w.r.t D. E [1, 10, 100)).
tends to collect less (but enough) data, which turn leads to more communication rounds and worse regret. The side-effect of the increased communication frequency is the higher payment costs, with respect to the gap requirement in each communication round. This particularly notable more collaborative environment, where clients have lower data sharing costs. As exemplified in Figure 4(c) when the clients
willing to share data (e.g.. D. = 1), the variants without PF incur significantly higher payment costs compared to the those with PF, as the server misses the opportunity get those easy motivate clients. Therefore, providing data incentives becomes more crucial in such scenarios to ensure effective client participation and minimize payment costs. On the other hand, the variants without iterative search (IS) tend to maintain competitive performance compared to the fully-fledged model, despite incurring a higher payment cost, highlighting the advantage of IS in minimizing payment.
E.3
Environment & Hyper-Parameter Study (Supplement to Section 5K
25, Dg Xeding
log,
DisLiaUCB
INC-FEDUCB (3 1)
INC-FEDUCB (3 0.7)
INC-FEDUCB (ā 0.3)
Reward (Acc.)
38,353
38,353
37,731 (A 1.6%)
36,829 (A 2.4%)
MovieLens
(D2
Commu, Cost
33,415,200
33,415,200
5,967,000 (A 82%)
2,457,000 (A 92.6%)
Cost
0. 0%)
( (%)
Reward (Ace.)
38,353
37,717 (2. 1.7%)
36,833 (A 419)
MovieLens
Commu, Cost
33,415,200
13.372.250 (A 609)
5,038,6755 (A 84.9%)
Pay.
124.41
0.0 10056)
Reward (Ace.)
1
38,353
37.648 (A) 1.89%)
36.675 (A 4.4%)
Moviel.nns (D' = 10)
33,415,200
10,41.250:00
709))
4,2401625 (A 87.35)
Pay. Cosl
110.737.62
8,590.43
02.2%)
2,076.98
98. 190
Rogret
38.353
37,641 (A. 1.995)
36.562
4.7%)
(D) 100)
Commu,
33,415,200
8,496 (A 74.6%)
5,136,70
84.6%)
Pay. Cost
1,155,616.99
105.847.84 (A 90.8%)
32,618.34 (A 97.2%)
Table 2: Study on parameee of INC-FEDUCB and environment (w/ theoretical D.).
In contrast the hyper-parameter study synthetic dataset with fixed communication threshold reported in Section 5.3, in this section, we comprehensively investigate the impact of 33 and D. on the real-world dataset by varying the communication thresholds D.. First, we empirically validate the
effectiveness of the theoretical value of D. N=dlog
No introduced in Theorcom
T2
The results presented Table 2 are generally consistent with the findings in Section 5.3) decreasing can substantially lower the payment cost while still maintaining competitive rewards. We can also find that using the theoretical value D, can also save the communication cost. This results from the fact that setting D. as function of 3 leads to higher communication threshold for lower B, and therefore reducing communication fireueeccy. This observation essentially aligned with the intuition behind lower 3: when the system has higher tolerance for outdated sufficient statistics, it should not only pay less in each communication round but also trigger communication less frequently.
On the other hand, we investigate INC-FEDUCB's performance under two fixed communication thresholds D. = TTNN2 d and D. T/(N To),, which are presented in Table 3 and
20

---

== K 25, D. Wallo
DisLinUCB
INC-FEDUCB (3 =
INC-FEDUCB (3 0.7)
INC-FEDUCB (3 = 0.3)
Reward (Aoc.)
38,353
38,353
38,353 0%)
38,353 (A 0%)
MovieLens (D 0)
Commu. Cost
33,415,200
33,415,200
33,415.200 (À 0%)
33,415,200 (A 0%)
Pay. Cost
0
0 = 09%)
( 0%)
Reward (Acc.)
38.353
38,207 (A 0.4%)
38,208 (A 0.4%%
MovieLens (D 1)
Commu. Cost
33,415,200
171,046,600 (A + 412%)
191,280,875 (A + 472%%
Pay. Cost
7859.67
2095.73 (A 73.3%)
36.32 (A) 99.5%)
Reward (Acc.)
38,353
38,251 (A. 0.3%)
37,609 (A 1.9%)
MovieLens (D = 10)
Commu, Cost
33,415.200
135,521,025 (A + 306%)
424,465,650 (A. 1170%)
Pay. Cost
110,737.62
33,271.39 70%)
33,872.78 09.4%)
Reward (Acc.)
38.353
38,251 (A. 0.3%)
37,970 (A 15))
MovieLens (D 100)
Commu. Cost
33,415,200
135,521.025 (A + 306%)
522, 196.229 (A + 1466%)
Pay. Cost
1,155,616.99
352,231.39 (A 69.5%)
346,619.77 (A. 70%6
Table 3: Study on hyper-parameter of INC-FEDUCB and environment (w/ lower fixed Da).
25, K
Da
N
DisLinUCB
INC-FEDUCB (8
INC-FEDUCB 0.7)
INC-FEDUCB (3 0.3)
Reward (Ace.)
37,308
37.308
37,308 (á 0%)
37,308 (Á 0%)
MovieLens
Commu. Cost
2,737,800
2,737,800
2,737,800 (A = 0%)
2,737,800 (A 0%)
(D
Pay. Cost
( 0%)
0 = 0%)
Reward (Acc.)
37,308
37,296 (A 0.1%)
37,306 (A 0.1%)
MovicLens
Commu. Cost
2,737,800
4,197,525 (4 53.3%)
5,948,950 (A + 117.3%)
(D
Pay. Cost
55.31
44.76
19.19%)
(4 10092)
Reward (Acc.)
37.308
37,297 (A 0.1%)
37,167 (A 0.1%)
MovieLens
Commu. Cost
2,737.800
3,696.350 (A 35%)
5,765,075 (A + 110.6%)
(D?
Pay. Cost
40148.69
3779.77 (A 6.6%)
2242.22 (A 44.6%)
Reward (Acc.)
37.308
37,273 (A 0.1%)
36,946 (A 0.1%%
MovieLens (DE 100)
Commu. Cost
2,737,800
3,484,850 (A. 27. 27.3%)
5,690,250 (A + 107.8%)
Pay. Cost
77.041.04
65,286.90 (A 15.3%)
40,010.59 (A 48.1%)
Table 4: Study on paraamerr of INC-FEDUCB and environment (w/ higher fixed D.).
respectively. These two values are created by increasing the thcoretical value of D Overall, the main findings align with those reported in Section 5.3 confirming previous statements. While reducing can achieve competitive rewards with lower payment costs, comes the expense of increased communication costs, suggesting the trade-off between payment costs and communication costs. Interestingly, the setting under higher D and D. can help mitigate the impact of f3. Specifically, while increasing the client's cost of data sharing inherently brings additional incentive costs, raising the communication threshold results in fewer communication rounds, leading reduced overall communication costs. This finding highlights the importance of thoughtful design in choosing D. and balance the trade-off between payment costs and communication costs in real-world scenarios with diverse data sharing costs.
E.4 Extreme Case Study
To further investigate the utility of INC-FEDUCB in extreme cases, we conduct a set of case studies on both synthetic and real-world datasets with fixed data sharing costs. As shown in Table 5 and o when | is extremely small, can achieve almost 100% savings in incentive cost compared the case where every client has to be incentivized to participate in data sharing (i.e., 3 =3=1) However, this extreme setting inevitably results in considerable drop in regret/reward performance and potentially tremendous extra communication cost due to the extremely outdated local statistics in clients. Nevertheless, by strategically choosing the communication threshold, we mitigate the additional communication costs associated with the low 3 values. For instance, in the synthetic dataset, the difference in performance drop between the theoretical D. setting and heuristic D. value
21

---

d- 25, 26, 100
Usc PaOUCB (f
Lsc INC-PEDUCB 67 6.7)
INC-Po (3 0.30
Tsc: INc-PRDUCB.C 0,00)
Repiet (Ace.)
45,37
46.33 (A 2.1%)
48.49 (A a 6,9%)
$1.22 + 12,959
T- 5000 N. 50
Canma Coo
174,720,000
264.198,273 (A 5L.2%)
299,134,500 (A 11,25)
314,667,500
80.15
479,397.18
229,99966
00%)
15,56)
42,800
91.178)
Regect (Aoc.)
66.72
49.15 (-835)
16,00
(0, T porrar 3og
17,806722
18,55)
Pay: Chud
469,397.18
178895 7 (A 62.78
84,98039
52335)
1,000 90.55)
Table Case study on synthetic dataset.
25,8
(3
IND-PRotiCI& 6.7)
INc-PERLICR 9.01)
35,253
38,251
0,3%)
57,700
18)
57,099
Movielaes
Comma Coe
18415,300
195,520025 (A 3000
532
( 1003))
1.206741 (2 3591-85)
Pay. Con
1.155,616.9
$52,331 (9 50.500
10%)
75,799 39 (A 56 $6.450
Rowani (Aac))
36,353
37,641 (A 1.55
36,982
(.75)
31,573 (3. 16.9%)
(1) ViN" aR -ogg))
MavieLass
33,415,200
9,496,000 (A 74.8%)
5.136,000
94.55)
1,80450044
94.4%)
Uost
1,155,616.9
59
90303)
32,61836
17 275)
200/3
99-166
Table Case study on real-world dataset.
is relatively small (A + 18.4% vs. A + 12.9%). However, these two different choices of De exhibit opposite effects on communication costs, with the theoretical one achieving a significant reduction (A - 98.3%) while the heuristic one incurred significant increase (A + 80.1%). On the other hand, in the real-world dataset, the heuristic choice of Da may lead to a smaller performance drop compared to the theoretical setting of De (e.g., A 3.4% vs. A 16.9%). reflecting the specific characteristics of the environment (e.g., a high demand of up-to-date sufficient statistics). Similar to the findings in Section E.3 this case study also emphasizes the significance of properly setting the system hyper-parametes and D.. By doing so, we can effectively accommodate the trade-off between performance, incentive costs, and communication costs, even in extreme cases.
F
Notation Table
Notation
Meaning context dimension total number of clients total number of time steps hyperparameter that controls the regret level
N
8
De
communication threshold data sharing cost of client i participant set at time step t data offered by the sever to client i at time step data/monetary incentive for client i at time step &
D.
S.
(SA(S))
Vi
covariance matrix constructed by all available data the system local data of client at time step f
Via. bis
Va bag
global data stored at the server time step data stored at client i that has not been shared with the server data stored at the server that has not been shared with the client i
AVa. Abie
AV 1,l
Ab-ia
Table 7: Main technical notations used in this paper.
22


Reviews:
[{"review_id": "9Sx63yd8EY", "reviewer": "Reviewer_zWH8", "summary": "This paper introduces an incentivized communication problem for federated bandits. They study the contextual linear bandit setting and propose the first incentivized communication protocol, namely, INC-FEDUCB, that achieves near-optimal regret with provable communication and incentive cost guarantees.", "questions": "It might be great to add some high-level idea of the proofs for the theorems.", "limitations": "They assume all clients truthfully reveal their costs of data sharing to the server.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper is well-organized. The problem studied in the paper is novel and important. They provide both technical results and empirical experiments on both synthetic and real-world datasets.", "weaknesses": "The paper lacks intuitive explanations for the technical results.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the appreciation of our work, and the constructive suggestions to enhance the presentation of our theoretical results.\n\n**[Q1]**: The paper lacks intuitive explanations for the technical results. It might be great to add some high-level idea of the proofs for the theorems.\n\n\n**[A1]**: Thanks for pointing out the places where we can make our paper more friendly to readers with diverse backgrounds. Below, we comprehensively summarize the intuition behind our algorithm design, as well as providing explanations of the main theoretical results.\n\n**Payment-free vs., Payment-efficient Mechanism Design**: \nAs we explained in Section 4.2, maximizing the determinant of the client’s local data $V_{i, t}$ directly corresponds to reducing its regret in this federated bandit problem. This principle drives the design of our metric defined in Eq(4): the greater the server’s offer (denoted as $D_{i,t}(S_t)$) can increase the determinant of the client’s local data, the higher incentive it can provide. But as we proved in Theorem 3, the payment-free mechanism might not motivate any client to participate under specific circumstances. To address this issue, the payment-efficient incentive mechanism introduces additional monetary incentives to motivate clients. And to avoid trivially paying everyone more than enough, we look for minimum incentive cost to achieve the desired level of regret, controlled by the hyperparameter $\\beta$. This poses a challenging optimization problem, as a brute-force search solution can yield a time complexity up to $O(2^N)$; and we implement a heuristic-based search (Algorithm 3) to minimize the incentive cost, with a time complexity of only $O(N)$.\n\n**Theorem 3**:  As detailed in Appendix C, the data incentive is bounded by the environment configuration. Thus, when client $i$’s cost $D^p_i$ exceeds this bound, it becomes impossible for the server to provide enough incentive to motivate client $i$ to participate in the communication. Theorem 3 implies that when the number of participating clients is less than the threshold $\\frac{c}{2C} \\cdot \\frac{N}{\\log(T/N)}$, a sub-optimal regret of the order $\\Omega(d\\sqrt{NT})$) (i.e., no regret reduction) is inevitable.\n\n\nThe proof of Theorem 3 relies on Lemma 8, which indicates that once we encounter a situation where the number of participants in the payment-free mechanism falls below a threshold, a sub-optimal regret is inevitable. Therefore, we first establish a data incentive bound, and then create a situation specified in Lemma 8, which completes the proof.\n\n**Communication Cost**: As detailed in Appendix D (Line 519), the communication cost is $C_T = P \\cdot O(Nd^2) = O(N^2 d^3 \\log T)$, where $O(Nd^2)$ is the communication cost per epoch, and $P = O(Nd\\log T)$ is the number of communication epochs, given the communication threshold $D_c = \\frac{T}{N^2d\\log T} - \\sqrt{\\frac{T^2}{N^2dR\\log T} }\\log \\beta$. This result suggests that a lower value for $\\beta$ results in a higher communication threshold $D_c$, thus leading to reduced communication frequency and cost, which is also supported by our numerical experiments (Appendix E.3). \n\nTo bound the communication cost, we first analyze the communication cost per epoch, then establish an upper bound for the total number of epochs, thereby completing the proof.\n\n\n**Regret**: As explained in Appendix D (Line 567), the regret is analyzed under good epochs and bad epochs of communication. Our result $R_T = R_{good} + R_{bad} = O\\left ( \\frac{d }{\\sqrt{\\beta}}\\cdot \\sqrt{T} \\cdot \\sqrt{\\log\\frac{T}{\\delta} \\cdot \\log T}\\right) + O\\left(Nd^{1.5}\\sqrt{D_c \\cdot \\log\\frac{T}{\\delta}}\\log T \\right)$ shows that a larger value of $\\beta$ leads to smaller regret in good epochs (first term), as the client’s local data gets closer to the global oracle. Meanwhile, a larger communication threshold $D_c$ results in worse regret in bad epochs (second term). This is because a higher communication threshold causes less frequent communications, ultimately resulting in worse regret.\n\n**Incentive Cost**: As detailed in Appendix D (Line 527), the incentive cost $M_T \\leq \\max_{i\\in[N]}\\{D_i^p\\} \\sum\\limits_{p = 1}^P N_p - \\sum\\limits_{i=1}^N\\sum\\limits_{p \\in \\mathcal{\\bar{P_i}}} \\mathcal{I}^{d}_{i, t_p}$ consists of two parts. The first part represents the case where the server only uses money to motivate clients in each communication epoch, disregarding the data incentive. The second part represents how much monetary incentive the server could have saved by motivating clients with data incentive. With the proper $D_c$, a lower value of $\\beta$ not only leads to less communication frequency but also decreases the demand for the server to collect data from the clients in each epoch, jointly resulting in reduced incentive cost, which is verified in our numerical experiments (Appendix E.3). \n\nTo derive this bound, we first analyze the monetary incentive cost by associating it with the client’s data sharing cost and the data incentive already provided by the server. Then, by establishing a lower bound for the data incentive, we can upper bound the incentive cost.\n\n**[Q2]**: They assume all clients truthfully reveal their costs of data sharing to the server.\n\n**[A2]**: Please find our answer to CQ1 in the general response to all reviewers. "}, {"review_id": "3piOirpJYZ", "reviewer": "Reviewer_rmwW", "summary": "The paper studied the problem of incentivizing data sharing in federated learning under the linear contextual federated bandit model with self-interested clients. While most previous works in federated bandit assume that all clients are willing participants in model sharing, this assumption is often unrealistic and neglects the inherent cost of data sharing for each client. The author proposed a general framework INC-FEDUCB that achieves near-optimal regret and provided upper bounds on the monetary and communication cost. Finally, the author provided empirical experiments to evaluate their mechanisms in different environments.", "questions": "- Can the current assumption on the cost function be relaxed by making a more explicit assumption on the form of the cost function for each client that account for the data-generating cost, communication cost, privacy cost, etc?", "limitations": "- The authors have addressed the limitation of the public cost vector. However, the author did not address the potential fairness issue that can come up with their monetary payment mechanism.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "- The studied problem of incentives in federated bandit learning is interesting and novel. \n- The theoretical claims are strong contributions. \n- The payment-efficient mechanism, while using a heuristic method, provides an improvement over the naive method.\n- In general, the paper is easy to read. \n- The provided empirical experiments support the theoretical claims.", "weaknesses": "- The paper made an important assumption that the server knows the vector of cost values exactly as an input to the incentive mechanism. This assumption relies on clients truthfully reporting their personal costs, which can be leveraged by adversarial clients who purposefully misreport their costs in order to game the incentive system. Also, since an objective of federated learning is to protect the privacy of participating clients, relying on clients to disclose their personal costs seems unrealistic.\n\n- Figures 1 and 2 do not have error bars. \n\n- There are some minor typos in the paper.\n\n- The monetary incentives might also come with some negative societal consequences, where clients are ranked by their potential contributions. There could be a scenario where clients are not selected due to their background and raise a fairness issue (e.g.: less-fortunate hospitals in a federated network that have fewer samples and thus do not contribute much are also less likely to be paid).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the constructive suggestions to clarify the important problem formulations, improve the presentation of results, and strengthen the discussion on the broader societal impact on fairness.\n\n**[Q1]**: The paper made an important assumption that the server knows the vector of cost values exactly as an input to the incentive mechanism. This assumption relies on clients truthfully reporting their personal costs, which can be leveraged by adversarial clients who purposefully misreport their costs in order to game the incentive system. Also, since an objective of federated learning is to protect the privacy of participating clients, relying on clients to disclose their personal costs seems unrealistic.\n\n**[A1]**: Thanks for pointing out the place that could cause unnecessary confusion. Please find our answer to CQ1 in the general response to all reviewers. \n\n**[Q2]**: Figures 1 and 2 do not have error bars. \n\n**[A2]**: Thanks for the great suggestion! We have updated the figures with error bars. Please refer to the supplementary PDF for rebuttal. \n\n**[Q3]**: There are some minor typos in the paper.\n\n**[A3]**: Thanks for your careful review! We have thoroughly examined the paper and corrected the typos in the updated version.\n\n**[Q4]**: The monetary incentives might also come with some negative societal consequences, where clients are ranked by their potential contributions. There could be a scenario where clients are not selected due to their background and raise a fairness issue (e.g.: less-fortunate hospitals in a federated network that have fewer samples and thus do not contribute much are also less likely to be paid).\n\n**[A4]**: Thanks for the valuable comments! We would like to clarify that in the federated bandit problems, the clients’ primary goal is to minimize their regret [1,2,3,4]. According to our Algorithm 1, all clients (no matter whether they get paid or not) will receive the same amount of data after each communication for better arm selection (thus minimizing regret). Therefore, there is **NO** fairness issue in the sense of regret minimization.  In fact, our incentive design is reasonably fair for both sides of the problem: 1. From a rational individual’s perspective, only those who suffer from data sharing (e.g., potential cost of privacy) will get monetary compensation; 2. From the system designer’s perspective, all clients are helped equally by the system in terms of regret minimization.\n\nFollowing the reviewer’s hospital example, a client (hospital) minimizing its regret can be interpreted as providing better treatment to its patients. Based on our incentive mechanism design, all hospitals will receive the same improvement of treatment quality by our federated bandit learning solution, therefore ensuring fairness in terms of helping patients. Although it may result in different hospital revenues, as some hospitals get more payments from the server, revenue distribution is beyond the scope of our work. \n\nWith that being said, we absolutely agree fairness could be a concern in some application problems, e.g., when maximizing monetary utility is also part of the client’s objective. Additional treatment is then needed from the system side for fairness in this regard, e.g., providing extra monetary incentive even when data incentive is enough to motivate the client for participation. As also mentioned in the ethical review, enforcing fairness is undoubtedly an important issue in not only our problem setup, but more generally in modern machine learning. The present work primarily focuses on developing methods to incentivize communications for more efficient federated learning. We plan to add a discussion on potential fairness issues our methods may potentially cause to some specific applications, though developing systematic methodologies to address this issue seems out of the scope of our work.\n\n**[Q5]**: Can the current assumption on the cost function be relaxed by making a more explicit assumption on the form of the cost function for each client that account for the data-generating cost, communication cost, privacy cost, etc?\n\n**[A5]**: Thanks for the insightful suggestion! We would like to clarify that our current cost function is not limited to any specific cost forms, such as communication resource consumption, data production cost, or potential privacy loss. Instead, it is a general design that jointly considers multiple aspects and is represented by a scalar (as introduced in Section 3.2). As the reviewer suggested, we completely agree that it would be more flexible to further customize the cost function by making assumptions on fine-grained cost forms, especially when our method is applied to different scenarios where certain aspects may be prioritized over others. For example, study the case where the data sharing cost for each client is based on the amount of local data it possesses or cost varies by different clients’ productivity. Unlike the fixed cost setting, this dynamic cost may introduce more difficulties in incentive cost analysis, and we believe it's a worthwhile future direction to explore more cost function designs.\n\n**[Q6]**: The authors have addressed the limitation of the public cost vector. However, the author did not address the potential fairness issue that can come up with their monetary payment mechanism.\n\n**[A6]**: Please find our answer to Q4 in the above response. \n\n**References**\n\n[1] Yuanhao Wang, Jiachen Hu, Xiaoyu Chen, and Liwei Wang. Distributed bandit learning: Near-optimal regret with efficient communication. ICLR 2020\n\n[2] Ruiquan Huang, Weiqiang Wu, Jing Yang, and Cong Shen. Federated linear contextual bandits. NeurIPS 2021.\n\n[3] Chuanhao Li and Hongning Wang. Asynchronous upper confidence bound algorithms for federated linear bandits. AISTATS 2022.\n\n[4] Chuanhao Li, Huazheng Wang, Mengdi Wang, and Hongning Wang. Learning kernelized contextual bandits in a distributed and asynchronous environment. ICLR 2023."}, {"review_id": "oWEk7MeC5M", "reviewer": "Reviewer_NbUe", "summary": "This paper introduces a novel federated learning protocol, so that 1) the setting is online instead of the more common offline setting, and 2) during each iteration, each client only chooses to participate (sharing information with the central server) if the client is gaining a sufficient amount of utility via participation through an incentive mechanism. The second property is particularly interesting because in the traditional setting, every client unconditionally participates and exchanges information with the central server, while in reality they may be reluctant because of low potential benefits. To ensure sufficient number of participants during every iteration, the central server may also provide extra support to motivate some clients. Finally, the protocol obtains near-optimal regrets and reasonable communication and incentive costs.", "questions": "The questions are listed in the weaknesses section.", "limitations": "I did not find any concerns in this regard.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 4, "strengths": "1. The topic is important and the mechanism based upon monetary and non-monetary incentives is novel.\n\n2. The paper is generally well-written, with convincing support for the motivation. It also covers an extensive literature as references to earlier works in this area.\n\n3. Such incentive mechanism may be well applied to other related areas.\n\n4. The theoretical argument is extensive. However, please take a look in the weaknesses and questions section.", "weaknesses": "1. We may need a more organized guide to notations in such a paper with a large number of variables. In particular, I didn’t find the definition of $g$ in $V_{g,0}$ and $b_{g,0}$ in the line 1 of algorithm 1. The same is in line 15: what do the negative subscripts $-j$ mean?\n\n2. The bar of utility for the participation standard did not have sufficient support: in line 9 of algorithm 1, why are the determinants of those matrices a good standard for a client to decide whether to participate or not?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the constructive suggestions to clarify data valuation design and improve the organization of notations.\n\n**[Q1]**: We may need a more organized guide to notations in such a paper with a large number of variables. In particular, I didn’t find the definition of $g$ in $V_{g,0}$ and $b_{g,0}$ in the line 1 of algorithm 1. The same is in line 15: what do the negative subscripts $-j$ mean?\n\n**[A1]**: Thanks for the great suggestion! Following the standard notation in the literature [1], $V_{g,t}, b_{g,t}$ represents the global (g) sufficient statistics stored in the server at time step $t$. The negative subscripts $V_{-j, t}, b_{-j, t}$ represent the aggregated updates stored at the server that have not been sent to client $j$. As suggested by the reviewer, we have added a notation table for the main technical notations. Please refer to the supplementary PDF for rebuttal (in our general response to all reviewers).\n\n**[Q2]**: The bar of utility for the participation standard did not have sufficient support: in line 9 of algorithm 1, why are the determinants of those matrices a good standard for a client to decide whether to participate or not?\n\n**[A2]**: We should clarify the confusion. A client decides to participate only if the incentive offered by the server exceeds its cost, as defined in Eq(1). Line 9 of algorithm 1 does **NOT** imply the decision of participation but rather serves as an event trigger for communication (see detailed description at Line 201 in Section 4.1). As highlighted in Algorithm 1, once a communication event is triggered, all clients will upload their $\\Delta V_{i,t}$ to the server (Line 10 of Algorithm 1) so as to compute potential incentives for clients. After that, the client will upload its corresponding $\\Delta b_{i,t}$ only if the incentive offered by the server is deemed to exceed its data sharing cost (Line 13 of Algorithm 1). Note that this design does not compromise clients’ privacy because only having $V_{i,t}$ is insufficient to update the model and the clients’ secret essentially lies in $\\Delta b_{i,t}$, as explained in Section 4.1 (Line 212). For a further discussion on the data valuation design, please find our answer to CQ2 in the general response to all reviewers. \n\n**References**\n\n[1] Chuanhao Li and Hongning Wang. Asynchronous upper confidence bound algorithms for federated linear bandits. AISTATS 2022.\n"}, {"review_id": "NDo5Y43cgt", "reviewer": "Reviewer_U6am", "summary": "The authors study a new problem in federated bandits that involves incentivizing clients to share data. They propose a solution called Inc-FedUCB, which offers incentives in a linear contextual bandit setting. They demonstrate that Inc-FedUCB can achieve near-optimal regret levels with guarantees on communication and payment costs. They also conduct extensive experiments to validate the effectiveness of their incentive designs in various environments.", "questions": "Please address the questions in weakness.", "limitations": "NA", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The paper is the first work that formulates and proves theoretical guarantees for the incentive design in federated bandit learning.\n2. Designing incentives to encourage collaborations among clients is important in federated bandit learning.\n3. The proposed algorithms are supported theoretically and numerically.", "weaknesses": "The paper's focus is on designing incentivized communication protocols. The contribution is meaningful but as mentioned by the authors in Line 51, a well-defined metric to measure the utility of data sharing is important. The current presentation related to the utility design is not clear. For example,\n  - Line 126: Did the authors assume that all the clients share the same $\\theta_{\\star}$? If true, the assumption might be strong.\n  - Eqn. (4): It seems that the value of new data is independent of $\\theta_{\\star}$. Again, does this need the assumption that all clients share the same $\\theta_{\\star}$? If not, the value should also depend on different $\\theta$ because some high-value data for client 1 may be useless for other clients.\n - Lemmas 5 and 7 seem to be important in designing the incentive but are deferred to Appendix.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the constructive suggestions to clarify problem formulation and data valuation design, as well as for helping us improve the overall organization of the paper.\n\n\n**[Q1]**: Line 126: Did the authors assume that all the clients share the same $\\theta_\\star$? If true, the assumption might be strong.\n\n**[A1]**: Thanks for pointing out the place that could cause unnecessary confusion. We want to clarify that in our work all the clients share the same $\\theta_\\star$, and this is actually the standard assumption and widely adopted in the federated bandits literature [1,2,3,4]. For a detailed discussion of our data utility design, please refer to our response to CQ2 in the general feedback provided to all reviewers.\n\n**[Q2]**: Eqn. (4): It seems that the value of new data is independent of $\\theta_\\star$. Again, does this need the assumption that all clients share the same $\\theta_\\star$? If not, the value should also depend on different $\\theta$ because some high-value data for client 1 may be useless for other clients.\n\n**[A2]**: As the first work of this new incentivized federated bandit problem, we start with the standard homogeneous clients setting [1,2,3,4], where clients share the same unknown reward parameter $\\theta_\\star$. In this way, the data valuation design does **NOT** require to be dependent on $\\theta_\\star$ since all clients are estimating the same $\\theta_\\star$, and this design aligns well with the client’s objective of regret minimization as explained in Section 4.2. \n\nWe absolutely agree that it is interesting to explore the heterogeneous setting where clients are associated with different $\\theta_\\star$. And depending on the problem assumption, our current data valuation design of Eq(4) may or may not apply to the heterogeneous setting. Please see a detailed answer to CQ2 in the general response to all reviewers.\n\n\n**[Q3]**: Lemmas 5 and 7 seem to be important in designing the incentive but are deferred to Appendix.\n\n**[A3]**: Thanks for the great suggestion! Due to space limit, after presenting our original contribution in the main paper, we had to make such compromises and leave existing important lemmas to the appendix. In the updated version (w/ more space), we will ensure better organization of the paper and address this concern adequately.\n\n**References**\n\n[1] Yuanhao Wang, Jiachen Hu, Xiaoyu Chen, and Liwei Wang. Distributed bandit learning: Near-optimal regret with efficient communication. ICLR 2020\n\n[2] Ruiquan Huang, Weiqiang Wu, Jing Yang, and Cong Shen. Federated linear contextual bandits. NeurIPS 2021.\n\n[3] Chuanhao Li and Hongning Wang. Asynchronous upper confidence bound algorithms for federated linear bandits. AISTATS 2022.\n\n[4] Chuanhao Li, Huazheng Wang, Mengdi Wang, and Hongning Wang. Learning kernelized contextual bandits in a distributed and asynchronous environment. ICLR 2023."}]

Author rebuttal:
# General response to the reviewers:

We sincerely thank all the reviewers for their thoughtful comments and constructive suggestions, which will significantly help us strengthen our paper. It is encouraging that all reviewers appreciate the novelty and importance of the studied problem and our proposed solution, with solid theoretical analysis (Reviewer zWH8, rmwW, NbUe, U6am), extensive numerical validation (Reviewer zWH8, rmwW, NbUe, U6am), and potential broader impact to other related areas where incentivized federated learning is needed (Reviewer NbUe, U6am).

There are also shared comments regarding truthful cost revealing and data utility design. Indeed, one of the intended goals of our work is to inspire further investigations into this new direction with more diverse settings, such as learning with strategic clients where truthful mechanism design is needed, and heterogeneous client settings where relevant data utility design is needed. And we agree with the reviewers that those are all important future directions. Next, we first provide our responses to these common questions (CQs), and endeavor to provide individual responses to each reviewer.

**[CQ1]**: Truthful cost revealing (Reviewer zWH8, rmwW)

**[CA1]**:  In this work, we introduce the incentivized communication problem for federated bandits. As the first work of its kind, we aim to establish a foundation and initiate the study with a simplified setting, where clients truthfully reveal their data sharing costs. But as we discussed in the conclusion section, the study of truthful mechanism design is a very interesting and important future work. Specifically, to prevent clients from strategically misreporting their costs to gain more utility (either monetary or data incentive) from the server, one potentially promising direction is to investigate truthful (also known as incentive-compatible) mechanisms like the Vickrey–Clarke–Groves (VCG) mechanism, under which being truthful is the best response for all clients. We firmly believe this will open up an interesting new field of studies in federated bandits and beyond. 

On the other hand, as Reviewer rmwW suggested, explicitly sharing individual costs may expose a side channel of privacy breaches. In practice, one promising solution is to avoid this direct revelation via secure computation. As the cost values are simple scalars, like prices, and the associated operations are simply comparisons, it will not incur high overhead in secure computation.

**[CQ2]**: Data utility design (Reviewer NbUe, U6am)

**[CA2]**: In federated bandit problems, the clients typically share the same unknown reward parameter $\theta_\star$, which is a standard setting in this line of research [1,2,3,4]. We followed this setting and refer to it as the homogeneous client setting. As illustrated in Eq(3) of our paper, the determinant ratio $\frac{\det(\widetilde{V}\_{t-1})}{\det(V_{i_t, t-1})}$ reflects the additional regret due to the delayed synchronization between client $i_t$’s local sufficient statistics $V_{i_t, t-1}$ and the global statistics $\widetilde{V}_{t-1}$. This argument has been recognized in prior works, e.g., Section 3.2 of [3], and is also theoretically supported by Lemma 5 and 7 of our paper. In other words, if all clients participate in data sharing in every time step, the ratio will be kept at 1, and thus every client essentially enjoys the optimal regret (discussed in Section 3.1). **Therefore, minimizing this ratio directly corresponds to reducing client $i_t$'s regret**. As a result, the proposed Eq(4) is a natural design of data valuation for homogeneous clients. In essence, if we denote the data valuation function as $f(x)$, where $x$ is the metric defined in Eq(4) that directly measures the value of data for regret reduction, our current design can be regarded as $f(x)=x$. For different application scenarios, we can further generalize it to any monotonic function $f(x)$ on top of this metric.

Furthermore, we should emphasize that Line 9 of Algorithm 1 is **NOT** where the clients decide whether to participate. Instead, it is the “communication trigger” - to ensure communication efficiency during the federated learning process. An event trigger is introduced to control the communication frequency as detailed in Section 4.1. 

We also acknowledge that there are also studies [3] that explore the heterogeneous client setting in federated bandits, where the unknown parameter $\theta_\star$ for each client consists of a globally shared component $\theta_\star^g$ and a unique local component $\theta_\star^l$. In this case, the data valuation design should be different from our current solution, because data valuation now depends on each client’s own $\theta_\star$, which is unknown to the server and clients. For example, we may need to assume the availability of additional knowledge about the relation among the set $\{\theta_\star\}$, or design strategies that estimate such relations on the fly. Alternatively, one simplified solution is to assume clients value the data only based on the shared component $\theta_\star^g$, and then the data valuation design will be essentially the same as our current choice. 

**References**

[1] Yuanhao Wang, Jiachen Hu, Xiaoyu Chen, and Liwei Wang. Distributed bandit learning: Near-optimal regret with efficient communication. ICLR 2020

[2] Ruiquan Huang, Weiqiang Wu, Jing Yang, and Cong Shen. Federated linear contextual bandits. NeurIPS 2021.

[3] Chuanhao Li and Hongning Wang. Asynchronous upper confidence bound algorithms for federated linear bandits. AISTATS 2022.

[4] Chuanhao Li, Huazheng Wang, Mengdi Wang, and Hongning Wang. Learning kernelized contextual bandits in a distributed and asynchronous environment. ICLR 2023.

Meta-review: This paper studies the problem of incentives in federated contextual linear bandits. The authors formalize the incentive problem and propose the corresponding mechanism to solve it. The authors also provide the regret guarantees and communication costs of the proposed method. This is a problem relevant for NeurIPS that has not been thoroughly studied before.

The reviewers are positive and agree that the problem and results are interesting. In addition, the authors were able to address the concerns of the reviewers in the discussion.

In light of this, I recommend the acceptance of the paper and encourage the authors to incorporate these discussions into the revision.
Decision: Accept (poster)