Incentivized Truthful Communication for Federated Bandits
Authors: Zhepei Wei
Chuanhao Li
Tianze Ren
Haifeng Xu
Hongning Wang
Venue: ICLR 2024 poster (2024)
Keywords: Contextual bandit
Federated learning
Truthful mechanism design
Primary area: learning theory
TL;DR: We introduce the first truthful incentive mechanism for federated bandits, where clients are incentivized to truthfully report costs for their best interests. The proposed Truth-FedBan guarantees near-optimal regret, communication and social costs.

Abstract: To enhance the efficiency and practicality of federated bandit learning, recent advances have introduced incentives to motivate communication among clients, where a client participates only when the incentive offered by the server outweighs its participation cost. However, existing incentive mechanisms naively assume the clients are truthful: they all report their true cost and thus the higher cost one participating client claims, the more the server has to pay. Therefore, such mechanisms are vulnerable to strategic clients aiming to optimize their own utility by misreporting. To address this issue, we propose an incentive compatible (i.e., truthful) communication protocol, named Truth-FedBan, where the incentive for each participant is independent of its self-reported cost, and reporting the true cost is the only way to achieve the best utility. More importantly, Truth-FedBan still guarantees the sub-linear regret and communication cost without any overhead. In other words, the core conceptual contribution of this paper is, for the first time, demonstrating the possibility of simultaneously achieving incentive compatibility and nearly optimal regret in federated bandit learning. Extensive numerical studies further validate the effectiveness of our proposed solution.

Published as a conference paper at ICLR 2024
INCENTIVIZED TRUTHFUL COMMUNICATION FOR FEDERATED BANDITS
Zhepei Weit* Chuanhao Lit
Tianze Ren
Haifeng Xu²
Hongning Wang!
University of Virginia UUiiversity of Chicago (tqf5qb, cl c15ev, tr2bx, hw5x) @vi rginia nia edu ha wwwgxu@cciccgg.o..... edu
ABSTRACT
To enhance the efficiency and practicality of federated bandit learning, recent advances have introduced incentives to motivate communication among clients, where a client participates only when the incentive offered by the server out- weighs its participation cost. However, existing incentive mechanisms naively assume the clients are truthful: they all report their true cost and thus the higher cost one participating client claims, the more the server has to pay. Therefore, such mechanisms are vulnerable to strategic clients aiming to optimize their own utility by misreporting. To address this issue, we propose an incentive compatible (i.e., truthful) communication protocol, named centive for each participant is independent of its self-reported cost, and reporting the true cost the only way achieve the best utility. More importantly, TRUTH- FEDBAN still guarantees the sub-linear regret and communication cost without any overhead. In other words, the core conceptual contribution of this paper is, for the first time, demonstrating the possibility of simultaneously achieving incentive compatibility and nearly optimal regret in federated bandit learning. Extensive numerical studies further validate the effectiveness of our proposed solution.
where the in-
INTRODUCTION
addresses the exploration-cxploitttii exploitation dilemma in interactive environments, where the learner repeatedly chooses actions and observes the correspond- ing rewards from the environment. Subject to different goals the learner, c.g., maximizing cumu- lative rewards (Abbasi- Yadkori et al. 2201 Auer et al. (0022) vs., identifying the best arm (Audibert) al. 2010. Garivier & Kaufmann| 2016), bandit algorithms have been widely applied in various weal-world applications, such as model selection (Maron & Moore 1993), recommender systems (Li al., 22100a b), and clinical trials (Durand al., (018).. Most recently, propelled by the increasing scales of data across various sources and public concerns about data privacy, there has been grow- ing research effort devoted to federated bandit learning, which enables collective bandit learning among distributed learners while preserving data privacy of each learner. Recent advances in this line of research mainly focus on addressing the communication bottleneck in the federated network, which leads to communication-efiiceeli protocols for both non-contextual (Landgren et al.) 2016 Martínez-Rubio et al. 2019 Shi al. 2020 Zhu al., 2021 and contextual bandits (Wang al. Huang et al. 2021 et al. 2022 2023) under various environment settings.
Bandit learning (Lttimore & Szepesvári 2020)
However, almost all previous works assume clients are altruistic in sharing their local data with the server whenever communication is triggered (Wang et al. 2020 Li & Wang 2002aa] He et al. 2022).
This limits their practical deployment in real-world scenarios involving individual rational clients who share data only if provided with clear benefits. The only notable exception is Wei et al. 2023), where incentive is provided to motivate client's 's participation in federated learning. Nevertheless, their protocol naively assumes the clients are truthful in reporting their participation cost; and thus, they simply calculate incentives by each client's 's claimed cost, leaving it as design flaw for strategic clients to exploit. Therefore, how to design an incentive compatible mechanism for federated bandits that ensures truthful reporting while still preserving the near-optimal regret and communication cost still remains an open research problem.
"Equal Contribution

---

Published as a conference paper at ICLR 2024
Method
Regret
Communication Cost
IR
IC
SC
DisLi nCCB
O(d/Tlog
O(N"dlogg])
x
x
x
Wang et al.
2020
Inc F e UCB
OdvVTlog T)
O(N2 1og
V
X
(Wei et al. 2023)
Truth-FedBar
O(d/Tlog
O(Nad log TogT)
/
(Our Algorithm
Table 1: Comparison with related works, where IR, IC and SC represent the guarantee of individual rationality, incentive compatibility, and social cost near-optimality, respectively.
Following Wei et al. (2023) 's setting for learning contextual linear bandits in a federated environ- ment, we develop the first incentive compatible communication protocol TRUTH- SOUTH--FEDAAAT FEDBAN, which ensures the clients can only achieve their best utility by reporting the true participation costs. Specif- ically, instead of simply paying a client by its claimed cost, we decouple the calculation of incentive from the target client's reported cost, while preserving individual rationality through eritical-valus based payment design that depends on all other clients' report cost. Besides the theoretical guaran- tee truthfulness, we also empirically demonstrate that misreporting cost brings no benefit to the client's utility. More encouragingly. we prove that this can be achieved without any compromise in maintaining the near-optimal performance in regret and communication cost.
On the other hand, in addition the above desiderata, maintaining minimal social cost is also an important objective in the incentivized communication problem, especially in practical applications. Following classical economic literature (Procaccia & Tennenholiz 2013), social cost is defined as the sum of true participation costs among all participating clients. While incentivizing all clients' participation ensures nearly optimal performance (Wang al., 2020), it be scientifically trivial (e.g.. paying everyone to have all of them participate) and practically undesirable - it not only brings unnecessary burden for the server, but can also expose unnecessary clients to potential down- sides of participation (c.g.. privacy breaches, added resource consumption, etc.). resulting in worse social cost. Minimizing social cost while ensuring sufficient client participation is non-trivial, as it in nature is NP-hard (see Eq. (I). Though the method proposed by WWei et al. (2023) achieves sub-linear regret and communication cost (albeit assuming truthfulness), it provides no guarantee on the social cost. In contrast, our proposed TRUTH-FEDBAN guarantees both sub-linear regret and near-optimal social cost, with only constant-factor approximation ratio. To better illustrate our contribution, we compare the proposed
with the most related works in Table
RELATED WORK
2.1 FEDERATED BANDIT LEARNING
Federated bandit learning has been well investigated for sequential decision making in distributed environments. These studies mainly differ in how they model the clients' and environment charac- teristics, which can be categorized into 1) bandil-wise:: problem profile (e.g., context-free (Martínez-
Rubio al. 2019 Shi & Shen| 2021; Shi et al.) 2020) vs. contextual (Wang al., 20200) and deci- sion set (e.g., fixed (Huang et al. 2021) vs. time-varying (Li & Wang 2022b)). and 2) system-wise: client type (e.g., homogeneous (He al., (022) vs. heterogeneous (Li & Wang] (022al) ). network type (c.g., peer-to-peer (P2P) (Dubey & Pentland 2020) vs. star-shaped (Wang et al. (2020), and
communication type (c.g., synchronous et 2022) vs. asynchronous (Li et al. (023)).
Most recently, Wei et al. (2023) expand this spectrum by introducing the notion of incentivized communication, where the server has to pay the clients for their participation. Despite being free from the long-standing assumption about the client's willingness of participation literature, they still assume truthfulness of clients in cost reporting. Specifically, their incentive calculation is based on the client's self-reported cost, which leads to serious vulnerability in adversarial scenarios as clients can exploit this flaw, ultimately paralyzing the federated learning system. This is particularly concerning in real-world applications where self-interested clients are motivated to strategically game the system for increased utilities, i.e., increase the difference between incentives offered by the server and actual participation costs. Our work aims address this issue by introducing truthful incentive mechanism under which clients reporting true costs is in their best interest, while ensuring near-optimal learning performance.
2

---

Published as a conference paper at ICLR 2024
2.2 MECHANISM DESIGN
Mechanism design NNsan & Ronen 1999) has been playing a crucial role in the fields of economics, computer science and operation research, with fruitful auction-like real-world applications such as matching markets (Roth, 1986). resource allocation (Procaccia) 2013). online advertisement pric- ing (Aggarwal et al., 2006). Typically, the auctioneer (server) aims to sell/purchase one more entries of a collection to/from multiple bidders (clients), with the objective of maximizing social welfare minimizing social cost. The goal of mechanism design is incentivize clients to truth- fully report the values of the entries (i.e., truthfulness), while ensuring non non-negative utilities if they participate in the mechanism (i.c., individual rationality).
The Vickrey-Clarde -aaa-CC-aarrorveeee Groves (VCG) mechanism (Vickrey] 1961; Clarke, 1971 Groves
1973) is
probably the most well-known truthful mechanism. Despite having been well explored in many theoretical studies, VCG is rarely applied in practical applications due to its computational ineffi ciency. This is because VCG requires finding an optimal solution to the concerned problem, which often NP-hard (Archer & Tardos (00T). Otherwise. truthfulness cannot be guaranteed when VCG mechanisms are applied to sub-optimal solutions (Lehmann et al.] 2002). To facilitate study on this issue, Musuue,MuuAaa AMu'Alem & Nisan (2008) identified the key character of a truthful mechanism and reduced the problem to designing a monotone algorithm (see Section [.1)). One notable recent related work is (Kandasamy al. 2023), where the authors model repeated auctions for the server, with e clients being unaware of their values but able to provide bandit feedback based on the server's allocation. The server's goal is to find allocations that maximize social welfare, while ensuring the clients' truthfulness in their feedback. In contrast, in our work, clients know their par- ticipation costs and concerned to solve the bandit problem collectively. The server's goal is to incentivize clients' participation for regret minimization, while ensuring the clients' truthfulness in cost reporting and minimizing social cost.
bandit learning problem
In terms of problem formulation, our work is closest to the hiring-a-leam task in procurement auc- tions [Talwar] 20033 |Archrr & Tardos] (007), where the server aims to incentivize a set of self- interested clients to jointly perform a task. One standard assumption in this task is that the envi- ronment is monoopllyffrec i.e., no single client exists in all feasible sets (Iwasaki et al. (007). The reason is that if a client is essential, it has the bargaining power to ask for infinite incentive. In this paper, we do not assume a monopoly tions will be needed (c.g., how the context or arms should distribute across clients). Instead, we are intrigued in studying the origin and impact of the monopoly issue from both theoretical and empiri- cal perspectives. And we also rigorously prove that control in our mechanism (see Lemma
environment, otherwise additional environment assump-
eliminate the issue via hyper- parameter
2.3 MECHANISM DESIGN IN FEDERATED LEARNING
On the other hand, there have been growing efforts in investigating mechanism design in the context of federated learning (Pei 2020 Tu et al. 2022). For example, Karimireddy et al. (2022) introduced a contract-theory based incentive mechanism to maximize data sharing while avoiding free-riding clients. In their design, every client gets different snapshots of the global model with different levels of accuracy as incentive, and truthfully reporting their data sharing costs is the best response under the proposed incentive mechanism. Therefore, there is no overall performance guarantee and their focus is on investigating the level of accuracy the system can achieve under this truthful incentive mechanism. [L et al. (2021) also investigated truthful mechanism design in the application scenario of wireless communication, where server's goal is to maximize the system's social welfare, with respect to knapsack upper bound constraint. In contrast, in our problem the server is obligated to improve the overall performance of the learning system, i.c., obtaining near-optimal regret among all clients. Furthermore, our optimization problem (defined in Eq. (3)) aims at minimizing the so- cial cost, with respect to a submodular lower bound constraint. Therefore, despite we share a similar idea of using the monotone participant selection rule and critical- -vlue based payment design to guarantee truthfulness. the underlying fundamental optimization problems are completely different, and consequently their solution cannot be used to solve our problem. Besides pursuing the truth- fulness guarantee in mechanism design under the collaborative/feddrrted setting, the other related line of research focuses on designing incentive mechanisms that ensures fairness among distributed clients (Blum et al., 2021 Xu et al., 2021 Sim et al.) 2020 Donahue & Kleinberg 2023), which is also an important direction, despite being beyond the scope of our work. To our best knowledge, our work is the first attempt that studies truthful mechanism design for federated bandit learnin..
3

---

Published as a conference paper at ICLR 2024
3 PRELIMINARY: INCENTIVIZED FEDERATED BANDITS
In this section, we present the incentivized communication problem for federated bandits in gen- eral and the existing solution framework under the linear reward assumption (Wang et al. 2020). More precisely, we focus our discussions on the learning objectives, including minimizing regret, communication cost, social cost, and ensuring truthfulness.
Consider a learning system with 1) N distributed strategic and individual rational clients that re- peatedly interact with the environment by taking actions to receive rewards, and 2) a central server responsible for motivating the clients to participate in federated learning via incentives. As in line with WWi et al.] (2023), we assume the clients can only communicate with the server, forming a star-shaped communication network. Specifically, at each time step E [T], an arbitrary client [N]] chooses arm X2 E A, from its given arm set A, S R. Then, client i, receives a reward V/ = =x f. + 77: E R, where H_ is the unknown parameter shared by all clients and 77; denotes zero- mean sub-Gaussian noise. Typically, in the centralized setting of bandit learning, a ridge regression estimator A. = Vo.i-1n, is constructed for arm selection based on the sufficient statistics from all N clients at time step where V E X,X, and bgg = E X.Y/,- In contrast, since commu- nication does not occur at every time step in the federated setting, each client only has a delayed copy of gg and bg.t, denoted as Ve, Vg guu + AVi.,, b,.t lig + Abi,. where V Vi gg.ha are the aggregated statistics shared by the server in the last communication, and A VV,,; Abi, are the accumulated local updates that client has collected from the environment since fasa-
Regret and Communication Cost One key objective of the learning system is to minimize the (pseudo) regret for all N clients across the entire time horizon T, i.e., Rr = Σi= Tr, where r. = maxxE.4, E Fyy x Elya xx] is the instantaneous regret of client in at time step f. Meanwhile, a low communication cost is also desired to keep the efficiency of federated learning. which measured by the total number of scalars transferred throughout the system up to time T. Intuitively, more frequent communication leads to lower regret. For example, communicating at every time step recovers the centralized setting, leading to the lowest regret, but with an undesirably high communication cost. Efficient communication protocol design becomes the key to balance regret and communication cost. And using determinant ratio to measure the outdatedness of the sufficient statistics stored on the server side against those the client side has become the reference solution to control communication in federated linear bandits (Wang et al. 2020 Li & Wang 2022a).
Incentivized Communication When dealing with individual rational clients, additional treatment is needed to facilitate communication, as becomes possible that no client participates unless prop- erly incentivized thus leading to terrible regret. In other words, client only participates if its utility Ug,t = It,-- D non-negative, where L,, the server-proc peoverdd incentive, and Dj,, the client's participation cost. To address this challenge and maintain near-optimal learning outcome, /Wei et al. 2023) pinpointed the core optimization problem in incentivized communication as follows:
min Σ Di, s.t. det(V,,:(S.) 2 S,C2$
(1)
det(VV,;(S)
IES.
where De,e is client i's reported participation cost, St is the set of clients selected to participate at time step I, 5 = {1, 2, .... ,N} is the set of all clients, / is specified as an input to the algorithm, and (S) = V, nm Ejes AVj.. e. In particular, they assume the clients' reported cost is simply the true cost, i.e., Dr,t Dr,,- A heuristic search algorithm is executed to solve the optimization problem whenever the standard communication event (Wang et al., 2020) is triggered. A detailed description of this communication protocol is provided in Appendix F
Note that Wei et al. (2023)'s 's work is limited a constant cost setting of D., = C. T(AV,. * 0), which restricts the actual cost Da.t of client i to be independent of time and its local updates A AV..- In our work, we relax it to Drt = f(AV where f can be any reasonable data valuation function, and even ' Moreover, their proposed solution for Eq. ( fails to provide any approximation guarantee on the objective, thus having no guarantee on the social cost. Below, we provide formal definition of truthfulness and social cost employed in this paper.
In fact, our proposed TRUTH-FEDBAN works with any realization of the valuation function, as all that matters that client á has value D., for its data at time step f.
4

---

Published as a conference paper at ICLR 2024
Definition (Truthfulness) An incentive mechanism is truthful (i.e., incentive compatible) if at any time I the utility u4, of any client is maximized when reports its true participation cost, i.e. Di, = Di,t regardless of the reported costs of the other clients' D
Definition (Social Cost) The social cost of the learning system is defined as the total actual costs incurred by all participating clients in the incentivized client set St, i.e, Lies, Di,t-
Note that the social cost defined above is different from the incentive cost studied in Wei et al. (2023), which is the total payment the server made to all clients. As truthfulness is assumed in their setting, the payment that the server needs to make to incentivize a client is trivially upper bounded by the client's 's true cost. However, in order to ensure truthfulness in our setting, the server needs to overpay the selected clients (compared with their true cost). In the case where there exists monopoly client as introduced in Section 2.2] an infinite incentive cost is required.
4 METHODOLOGY
4.1
CUARACTERRIZTTION OF TRUTHFUL INCENTIVE MECIIANISMS
Our idea stems from the seminal result Mu' Alem & Nisan 2008 who provided characteriza- tion of truthful incentive mechanism as a combination of a monotone selection rule and a critical value payment scheme, which reduces the problem of designing truthful mechanism to that of designing a monotone selection rule. Though it is originally intended for combinatorial auctions in economics, we are the first to extend it to the incentivized communication problem in federated bandit learning, laying the foundations for future work.
Definition 3 (Monotonicity) The selection rule for the set St is monotone if for any client i and any reported costs of the other clients D_i.y client will remain selected whenever it reports D'22= S Di.t provided it is incentivized when reporting Di,--
Furthermore, according to Mu' Alem & Nisan (2008), any monotone selection rule of the incentive mechanism has an associated critical payment scheme, with its definition given below.
Definition 4 (Critical Payment) Let M be monotone selection rule of the incentive mecha- nism and St be the set of selected clients, then for any client and any reported costs of the other clients D_i.t. there exists a critical value (.a(MDDisd) E (R2 U oo) such that i E S.. 4 VDD < (.M, D-i,), and & St, VD (MM, D=i.))
In this way, we can decouple the incentive Ii, for client i from its reported participation cost D.... and calculate the critical value based only on the other clients' reported costs D_ije. Formally,
I, = Cr (M, D_...) Il(i S:)
which is fundamentally different from the incentive design in (Wei al. 2023 where I,, Des- T(i E St), as our payment method leaves no room for strategic clients to manipulate the incentive and benefit from misreporting.
4.2 TRUTH-PEDBAN: A TRUTHFUL MECHANISM FOR INCENTIVIZED COMMUNICATION
To balance regret and communication cost, while ensuring truthfulness and minimizing social cost, our proposed incentive mechanism TRUTH-FEDB. inherits the incentivized communication pro- tocol by Wei et al. (2023), with the distinction in implementing a truthful incentive search. As stated above, the truthfulness of clients is ensured once we devise a monotone algorithm for client selec- tion. combined with critical payment scheme. But straightforward monotone algorithms (c.g.. greedy algorithm ranking clients by their claimed costs) offer no guarantee on social cost. To address this challenge, we rewrite the original optimization problem in Eq. ① into the following equivalent submodular set cover (SSC) problem, where g(S) is submodular set function (see Definition
det Vy,, (S.))
min Σ Dis s.t. (S.) 2 log 3, (S.) = log det (V,. (5)) S,E23 iES,
5

---

Published as a conference paper at ICLR 2024
Algorithm Truthful Incentive Search
Algorithm 2 GREEDY
Require: E > 0
Require: 5.b
St + 0. S 21, ,N]
1: S + 0 while Eies: Dis do
2: b + min Dis
3: while (St) < (1 e- 1 log 3 do
2:(8,0())=
4: b b- (1+ +cbb c)b
u
arg max
Djit
5: St + GREEDY(S, b)
4:
S
6: return Sb
5: return St
Inspired by [yer & Bilmes (203)), we propose Algorithm|| I that achieves constant-factor bi-criteria approximation for both the objective and constraint in the problem defined by Eq. (3). As outlined above, we first initialize minimal budget (Line 2) for social cost and repeatedly increase the budget (Line 4) until the resulting client set found by Algorithm satisfies the specified condition (Line 3).
In Algorithm 2 for a given budget 4, we iteratively find the best set of clients from the complete client set until the budget cannot afford more clients. At each iteration, all the remaining non- selected clients are ranked based on their contribution-to-con ratio (and hence being greedy). The algorithm then chooses the client with the highest ratio while ensuring the total cost of all selected clients is within the budget (Line of Algorithm 2). The correctness of our method hinges on the following crucial monotonicity property that we prove. Interestingly, despite the wide use of greedy algorithms in submodular maximization, this monotonicity result is unknown in previous literature to the best of our knowledge. We thus present it proposition in case it is of independent interest.
Proposition 5 (Monotonicity) Algorithm 7 is monotone.
is not difficult to show that Algorithm is monotone for a fixed input budget - that is, client i is selected under Di., by Algorithm it remains selected when it reports any Dí, S Di,-- But it is highly non-trivial to prove monotonicity for Algorithm T This is because decreasing client's reported cost can cause a different output by Algorithm 2 and, consequently, terminate the search process in Algorithm 1 at a different budget with potentially different selection of participant set S.. We prove Proposition by showing the resulting objective value gr (St) from Algorithm [ selection of clients non non-decreasing with respect to input budget b. The proof is bit involving since Algorithm ( is an approximate algorithm and generally outputs sub-optimal solutions. We will have show that the quality of these sub-optimal solutions from the exact optimality- - will not degenerate as the budget b increases. The proof of the above property, together with the formal proof of Proposition 5 can be found in Appendix A
which can be close to or far away
Lemma 6 If the selection rule of trushful mechanism is computable in polynomial time, so is the critical payment scheme (Mu' (Mu'Alem Nisan 2008
Note that in the star-shaped communication network, only the server has the necessary information to calculate the critical value of each client, and we assume the server is committed not to tricking the clients. Due to space limit, we leave the detailed critical payment calculation to Appendix G In particular, as we do not assume a monopoly-fre environment, a client's 's critical value could be infinite at certain point, as introduced in Section 2.2 Nonetheless, Lemma 7 shows that this infi- nite payment issue can be essentially eliminated by hy pyprr-parameter control. The time complexity
analysis of Algorithm can be found in Appendix
Lemma 7 (Elimination of Infinite Critical Value) With parameter 3 < (1 + LL2 /L2 in Algo- rithm 7 no client will be essential in any communication round at time step
A detailed proof is provided in Appendix D Building upon the properties above, we are now ready to state the main incentive guarantee of our TRUTH-FEDBAA protocol.
Theorem 8 The incentive mechanism induced by Algorithm 7 is (a) truthful in the sense that ev- ery client achieves the highest utility by reporting its true participation cost; and (b) individually rational in the sense that every client's 's utility of participating in the mechanism is non-negative.
6

---

Published as a conference paper at ICLR 2024
Proof The truthfulness guarantee directly follows Lemma 5 Below, further elaborate the impact of misreporting. Denote S, and St as the participant sets when client truthfully reports and misreports its data sharing cost as Di.- Di, and Di * Di,, respectively, Let Ci.t be the critical value of client i, and Us,t and v be its utilities in the above two conditions respectively. According to Definition 4 we have i E S, whenever Di..- < Ci.t, and i $ S whenever Di. > Ci,r- Moreover, if i & St, then ug,t = O. For simplicity, the subscript t is omitted in the following discussion. Specifically, there four possible cases: i) E S and E S", critical payment is independent from the client's s reported cost D. and D', therefore vi u, (c: D:) (c: D2) 0: 2) S
and E 5", in this case, D, = D. < C4 < D'. Therefore, v/: u, = (a- - -D:) = D. -
3) i g S and i E S", in this case, Dj < < < D; - D.. Therefore, un 04 = (G (20 - 4) i i S and i $ S", in this case. both utilizes are zero, therefore v/ u4 = 0 -0-0 0. To conclude, there is no benefit to misreport under our truthful mechanism design in all cases, and only reporting the true data sharing cost can lead to the client's best utility.
We now prove the individual rationality. Given the truthfulness guarantee, each client i reports its true cost Di,, Di,,, and only gets incentivized if Di, < Ct,-- Therefore, the utility of client i is Wi,r Ci DA. 0 if client gets incentivized; otherwise, Watt O. In either case, client is ensured to have a non-negative utility, which completes the proof.
4.3 LEARNING PERFORMANCE OF TRUTII-FDBBN PROTOCOL
The truthfulness property above helps the system induce desirable clients participation behaviors. under these client
In this subsection, we demonstrate the learning performance of behaviors. Our main results are the following guarantees regarding total social cost that the TRUTH- FEDBAN protocol has to suffer and the resultant regret guarantee it induces.
Theorem (Social Cost) For any e > O, using Algorithm 2 to search for participants in Algo- rithm 7 provides [1 + e. - -1= bi-criteria approximation solution for the problem defined Eq. (3). In other words, to maintain a social cost that is within a (1 ++) factor of the opti- mal value, it necessitates relaxation of the constraint by factor of (1 - -e Formally,
De Σ
Das and ge(S)) 2 (1 (1---1) -)-"go YESt
KES.
where St is the output of Algorithm
7 and S is the ground-truth optimizer of Eq.
Proof Denote the optimal objective value of Eq. 3 as OPT. For the solution St. we have OPT Eies; Dr. and ge (St) 2 log B. To simplify out discussions, we omit the subscript t and let Si, and b be the output set and terminating budget of Algorithm[]] for solving the problem in Eq. (3), and Sy and b' b/(1 + c) be the set and budget at the previous iteration before termination, then we have
{ ((Sw)) < (1 - 6 1)----1)og log
(SS)) 2 (1 (1-e-1) 2)
(5)
Denote Sp as the optimal solution for the subroutine search problem with budget D' (denote the prob- in Line of Algorithm aas SUBPROBLEM). According to Sviridenko (2004), the approximation ratio of Algorithm 2 for this SUBPROBLEM is (1 - e - i.e.
lem solved by Algorithm /
g(Sy) 2 (1 1 )))(())
(6)
Combining Eq. 44 and Eq. (6). we have g(S)) < log 3. Furthermore, we can show that OPT // by contradiction. Assuming OPT < b' then S* is feasible solution for the SUBPROBLEM, and thus g(S*) < s(St) log, 3. However, this contradicts the fact that ((S)) > log 3, OPT > R.
Hence, we can show that the objective value of solution S₁ satisfies the following inequality:
Σ b SE
(1 OPT
This, combined with Eq. 5 concludes the proof.
7

---

Published as a conference paper at ICLR 2024
Since Dr, D.. is guaranteed (see Theorem 8 Theorem 9 directly bounds the social cost as de- fined in Definition [ Note that as indicated by Theorem ! we can flexibly choose any desired level of social cost by adjusting the parameter which allows us to accommodate various computation resources practical scenarios. For example, in the case where computation is not limiting factor and the core objective is to minimize the social cost, we can set the factor (1 + to be almost 1, approaching the optimal social cost. Moreover, though this bi-criteria approximation slightly devi- ates from the constraint of the original problem in Eq. (3) it only incurs a constant-factor gap of
(1-e e)), and Theorem 10 shows that we still attain near-optimal regret and communication cost, despite this deviation (see proof in Appendix
Theorem 10 (Regret and Communication Cost) Under threshold B, with high probability the
communication cost of TRUTU-FEDBAN satisfies CT = O(Nd) - = O(N2d log T), where P = O(Nd T') is the total number of communication rounds, under the communication thresh- old D No N-ddlloog
T
T2
log, 3(1-==)) in Algorithm 0 where R [d + x.)).
Furthermore, by setting 3(--e11) 2 e the cumulative regret is Ry O (dvTlogT)
5 EXPERIMENTS
To validate our solution, create a simulated federated bandit learning environment with context feature dimension d = and = 25 clients sequentially interacting with the environment for a fixed time horizon T.. Due to space limit, more implementation details can be found in Appendix G The results, averaged over 5 runs, are presented alongside the standard deviation.
5.1 COMPARISON BETWEEN DIFFERENT TRUTHFUL INCENTIVE MECHANISMS
180
100
300
(a) Reg. & Commu. Cost
(b) Inc. & Social Cost
(c) TRUTH- FEDBAN
(d) Vanilla Greedy
Figure Comparison between FEDBAN and vanilla greedy incentive mechanism.
We compare TRUTH-FEDBAN with vanilla greedy algorithm (Algorithm 3). Despite Algorithm also induces a monotone mechanism (and thus truthfull, it does not admit any constant- factor ap- proximation guarantee, hence is less theoretically exciting compared
TRUTH-FEDBAR A com- prehensive analysis regrading this baseline method can be found in Appendix B As reported in Figure ((a) and Figure [[b) TRUTH-FEDBAL
achieved competitive sub-linear regret and commu- nication cost compared to DisL.n (Wang et al., (020). with lower incentive and social costs compared to the baseline greedy method, validating our theoretical analysis.
5.2 IMPACT MISREPORTING
Micro-level Study. In this experiment, we study how misreporting affects individual, in terms of the client's regret, incentive and utility. To do so, we randomly designate a client to keep misre- porting throughout the entire time horizon while keeping the others being truthful, and compare the corresponding outcome for this client. We take truth-report as the benchmark and plot the individ- ual's 's total regret, incentive, and utility on the same chart using the normalized score (the respective value divided by that under truth-report), along with the actual value on top of each bar. pre- and the greedy method demonstrate the ability prevent client from benefiting via misreporting. It is important that the incentive pay- ment (i.e., critical value) for the client is subject to the incentive mechanism and independent of its claimed cost. Therefore, though under-reporting may encourage the client be selected by the in- centive mechanism, its net utility essentially becomes negative. Meanwhile, despite over-reporting cost only undertakes the risk of being ruled out and losing incentives, it is surprising that this behav-
sented in Figure [[c] and Figure I(d) both BRUTH-FEDBAL
8

---

Published as a conference paper at ICLR 2024
(a) Regret
(b) Communication Cost
(c) Incentive Cost
(d) Social Cost
Figure 2: Overall impact of misreporting.
ior leads to a slightly higher utility under the vanilla greedy incentive mechanism. We attribute this to the reduced participation cost incurred by the client- the less it participates, the less it suffers.
Macro-level Study. As presented in Figure 2 we also empirically investigate how different levels of misreporting across the set of clients affect the entire federated learning system. Specifically, we vary the number of misreporting clients from 0% to 100% to investigate the impact on overall system performance, including regret, communication cost, incentive cost, and social cost. Gen- erally, as guaranteed by our communication protocol, the overall regret under different degrees of misreporting remains virtually identical to the situation when no client misreports. Meanwhile, the communication cost tends to increase when clients under report and decrease when they over report. This aligns with our algorithm's 's design, which selects clients based on their value-to-coss ratio (Line 3 in Algorithm 2. For example, when client under reports, its ratio increases, which increases its chance to be selected in communication, hence leading to an increased communication cost.
An interesting finding that might seem contradictory to discovery in the previous micro-level study is the overall impact of over reporting on incentive costs, which implies that the more clients over report, the higher the incentives they will receive. But our finding in the miero-level study sug- gests that over reporting brings no benefit to the client's 's individual utility under FADTANFEDBAN. We note that the observation in macro-level study is due to collusion among clients- once sufficient group of clients colludes, the server has to increase the critical value or even pay infin- ity. This actually rationalizes individual client's commitment to be truthful, they are unaware of others clients' decision on truthfulness. Meanwhile, this finding reveals the vulnerability of the incentivized truthful communication to collusion, leaving an interesting avenue for future work to explore. On the other hand, can be observed that both overreporting and underreporting hurt the social cost until the misreporting ratio reaches approximately 50%. This is interesting from the per- spective of societal divisions when the society equally divided into two parts, the social cost at its largest. And as division decreases, the cost becomes lower. For example, when the misreport- ing ratio reaches 100%, meaning that everyone in the system misreporting, the social cost resets the scenario where no one misreports, marking the establishment of a new stability in the system.
CONCLUSION
In this work, we introduce the first truthful incentivized communication protocol TRUTII-FEDBAN for federated bandit learning, where a set of strategic and individual rational clients are incentivized to truthfully report their cost to participate distributed learning. Our key contribution is design a monotone client selection rule and its corresponding critical value based payment scheme. We establish the theoretical foundations for incentivized truthful communication, under which not only the social cost but also the regret and communication cost obtain their near-optimal performance. Numerical simulations verify our theoretical results, especially the truthfulness guarantee, i.c., indi- vidual clients' utility can only be maximized when reporting their true cost.
Our work opens a broad new direction for future exploration. First of all, our truthful incentivized communication protocol is not only limited to federated bandit learning, but can be applied to gen- eral distributed learning environments where self- inf-rinteeeted clients need to be incentivized for col- laborative learning. Second, our truthful guarantee is proved for every round of communication, but it is unclear whether a client can do long-term planning to game the system. For example, keep over reporting until it becomes monopoly, ultimately leading to an infinite incentive for its participation. Last but not least, although we no longer assume clients are truthful, we still assume they are not malicious, i.e., they only want maximize their own utility. In practice, it necessary to investigate the problem under an adversarial context, e.g., malicious clients intentionally misreport their costs to hurt other clients' utilities or system's learning outcome.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
We thank the anonymous reviewers for their insightful and constructive comments. This project partially supported by NSF Award LIS-2213700 and IIS-2128019. Haifeng Xu is supported by an NSF Award CCF-2303372, Army Research Office Award W91 1011N-233-1-003 an Office of Naval Research Award N00014-23-1-2802 and A12050 program at Schmidt Sciences (Grant G-24- 66104).
REFERENCES
Yasin Abbasi-Yadkori, Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. In NIP,, volume 11, pp. 2312-2320, 2011.
Gagan Aggarwal, Ashish Goel, and Rajeev Motwani. Truthful auctions for pricing search keywords. In Proceedings of the 7th ACM Conference on Electronic Commerce, pp. 2006.
Aaron Archer and Êva Tardos. Truthful mechanisms for one-parameter agents. In Proceedings 42nd IEEE Symposium on Foundations of Computer Science, pp. 482-491. IEEE, 2001.
Aaron Archer and Êiva Tardos. Frugal path mechanisms. ACM Transactions on Algorithms (TAANTTAAAA) (TALG), 3(1):1-22, 2007.
Jean-Ye Yves Audibert, Sébastien Bubeck, and Rémi Munos. Best identification in multi-armed bandits. In COLT, pp. 41-53, 2010.
Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2):235-22) 2002.
Avrim Blum, Nika Haghtalab, Richard Lanas Phillips, and Han Shao. One for one, or all for all: Equilibria and optimality of collaboration in federated learning. In International Conference on Machine Learning, pp. 1005-1014. PMLR, 2021.
Richard L Burden, Douglas Faires, and Annette M Burden. Numerical analysis. Cengage learning, 2015.
Edward H Clarke. Multipart pricing of public goods. Public choice, pp. 17-33, 1971.
Kate Donahue and Jon Kleinberg. Fairness in model-sharing games. In Proceedings of the ACM Web Conference 2023, pp. 3775-3783 2023.
Abhimanyu Dubey and AlexSandy' Pentland. Differentially-ppivaae federated linear bandits. Ad- vances in Neural Information Processing Systems, 33:6003-6014, 2020.
Audrey Durand, Charis Achilleos, Demetris lacovides, Katerina Strati, Georgios D Mitsis, and Joelle Pineau. Contextual bandits for adapting treatment in mouse model of de novo carcino- genesis. Machine learning for healthcare conference, pp. 67-82. PMLR, 2018
Aurélien Garivier and Emilie Kaufmann. Optimal best arm identification with fixed confidence. In Conference on Learning Theory, pp. 998-1027. PMLR, 2016.
Theodore Groves. Incentives in teams.
Econometrica: Journal of the Econometric Society, pp-
617-631, 1973.
David A Harville. Matrix Algebra From Statistician's 's Perspective. Springer Science & Business Media, 2008
Jiafan He, Tianhao Wang, Yifei Min, and Quanquan Gu. 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 (eds.), Advances in Neural Information Processing Systems, Curran Associates, Inc., 2022.
volume 35, pp. 1762-47755
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 (eds.), Advances in Neural Information Processing Systems, volume 34, pp. 27057-27068. Curran Associates, Inc.,
2021.
10

---

Published as a conference paper at ICLR 2024
Atsushi Iwasaki, David Kempe, Yasumasa Saito, Mahyar Salek, and Makoto Yokoo. False-name- proof mechanisms for hiring a team. In Internet and Network Economics: Third International Workshop, WINE 2007, San Diego, CA, USA, December 12-14, 2007. Proceedings 3, pp. 245- 256. Springer, 2007.
Rishabh K Iyer and Jeff A Bilmes. Submodular optimization with submodular cover and submodular knapsack constraints. Advances in neural information processing systems, 26, 2013.
Kirthevasan Kandasamy, Joseph E Gonzalez, Michael I Jordan, and Ion Stoica. Veg mechanism design with unknown agent values under stochastic bandit feedback. Journal of Machine Learning Research, 24(53):1 1000):145,,222 2023.
Sai Praneeth Karimireddy, Wenshuo Guo, and Michael I Jordan. Mechanisms that incentivize data sharing in federated learning. arXiv preprint wwXiv:220.004557 2022.
Peter Landgren, Vaibhav Srivastava, and Naomi Ehrich Leonard. On distributed cooperative
decision- making in multiarmed bandits. In 2016 European Control Conference (ECC), pp. 243- 248. IEEE, 2016.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Tra Huong Thi Le, Nguyen H Tran, Yan Kyaw Tun, Minh NH Nguyen, Shashi Raj Pandey, Zhu Han, and Choong Seon Hong. An incentive mechanism for federated learning in wireless cellular networks: An auction approach. IEEE Transactions on Wireless Communications, 20(8):4874- 1887,202)
Daniel Lehmann, Liadan Ita Ocallaghan, and Yoav Shoham. Truth revelation in approximately efficient combinatorial auctions. Journal of the ACM (JACM), 4955)557662 2002.
Chuanhao Li and Hongning Wang. Asynchronous upper confidence bound algorithms for federated linear bandits. In International Conference on Artificial Intelligence and Statistics, pp. 6529-
6553. PMLR, 2022a.
Chuanhao Li and Hongning Wang. Communication efficient federated learning for generalized linear bandits. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, 2022b.
Chuanhao Li, Huazheng Wang, Mengdi Wang, and Hongning Wang. Communication efficient dis- tributed learning for kernelized contextual bandits. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, 2022.
Chuanhao Li, Huazheng Wang, Mengdi Wang, and Hongning Wang. Learning kernelized contextual bandits in distributed and asynchronous environment. The Eleventh International Conference Learning Representations, 2023.
I Lihong Li, Wei Chu, John Langford, and Robert Schapire. contextual- approach to personalized news article recommendation. In Proceedings of the 19th international conference on World wide web, pp. 661-670. 2010a.
Wei Li, Xuerui Wang, Ruofci Zhang, Ying Cui, Jianchang Mao, and Rong Jin. Exploitation and exploration in performance based contextual advertising system. In Proceedings of the 16th ACM SIGKDI) international conference on Knowledge discovery and data mining, pp. 27-36, 2010b.
Oded Maron and Andrew Moore. Hoeffding races: Accelerating model selection search for clas- sification and function approximation. Advances in neural information processing systems, 6, 1993.
David Martínez-Rubio, Varun Kanade, and Patrick Rebeschini. Decentralized cooperative stochastic bandits. Advances in Neural Information Processing Systems, 32, 2019.
Ahuva Mu' Alem and Noam Nisan. Truthful approximation mechanisms for restricted combinatorial auctions. Games and Economic Behavior, 64(2):612-631, 2008.

---

Published as a conference paper at ICLR 2024
Noam Nisan and Amir Ronen. Algorithmic mechanism design. In Proceedings of the thirty-first annual ACM symposium on Theory of computing, pp. 129-140, 1999.
Jian Pei. A survey on data pricing: from economics to data science. IEEE Transactions on knowledge and Data Engineering, 34(10):486-4608, 2020.
Ariel D Procaccia. Cake cutting: Not just child's play. Communications the ACM, 56(7):78-87, 2013.
Ariel D Procaccia and Moshe Tennenholtz. Approximate mechanism design without money. ACM Transactions Economics and Computation (TEAC), 1(4):1-26, 2013.
Alvin E Roth. On the allocation of residents to rural hospitals: general property of two-sided matching markets. Econometrica: Journal of the Econometric Society, pp. 425 427, 1986.
Chengshuai Shi and Cong Shen. Federated multi-armed bandits. In Proceedings of the AAAI Con- ference Artificial Intelligence, volume 35, pp. 9603-9611, 2021.
Chengshuai Shi, Wei Xiong, Cong Shen, and Jing Yang. Decentralized multi- multi-armed bandits with no collision information. In International Conference on Artificial Intelliencee and Statistics, pp. 1519-1528. PMLR, 2020.
Rachael Hwee Ling Sim, Yehong Zhang, Mun Choon Chan, and Bryan Kian Hsiang Low. Col- laborative machine learning with incentive-awarr model rewards. International conference on machine learning, pp. $927-8936. PMLR, 2020.
Maxim Sviridenko. A note maximizing submodular set function subject to knapsack straint. Operations Research Letters, 32(1):41-43, 2004.
Kunal Talwar. The price of truth: Frugality in truthful mechanisms. In Annual Symposium on Theoretical Aspects of Computer Science, pp. 608-619. Springer, 2003.
Xuezhen Tu, Kun Zhu, Nguyen Cong Luong, Dusit Niyato, Yang Zhang, and Juan Li. Incentive See mechanisms for federated learning: From economic and game theoretic perspective. IEEE trans- actions cognitive communications and neworking, 8(3):1566-159) 2022.
William Vickrey. Counterspeculation, auctions, and competitive sealed tenders. The Journal of finance, 16(1):8-37, 1961.
Yuanhao Wang, Jiachen Hu, Xiaoyu Chen, and Liwei Wang. Distributed bandit learning: Near- optimal regret with efficient communication. In International Conference Learning Represen- tations, 2020.
Zhepei Wei, Chuanhao Li, Haifeng Xu, and Hongning Wang. Incentivized communication for federated bandits. In seirth- Conference on Neural Information Processing Systems, 2023.
Laurence A Wolsey. An analysis of the greedy algorithm for the submodular set covering problem. Combinatorica, 2(4):385-33) 1982.
Xinyi Xu, Lingjuan Lyu, Xingjun Ma, Chenglin Miao, Chuan Sheng Foo, and Bryan Kian Hsiang Low. Gradient driven rewards guarantee faimess in collaborative machine learning, Advances in Neural Informatinn Processing Systems, 34:1610441611 16117, 2021.
Zhaowei Zhu, Jingxuan Zhu, Ji Liu, and Yang Liu. Federated bandit: gossiping approach. In Abstract Proceedings of the 2021 ACM SICMETRICS/hhtraatinnd Conference Measurement and Modeling of Computer Systems, pp. 3-4, 2021.
12

---

Published as a conference paper at ICLR 2024
A PROOF OF MONOTONICITY (PROPOSITION 5
Our proof of monotonicity relies on the submodularity property and the following lemma. Note that our proof holds true for any time step i, and thus the subscript is omitted below to keep our notations simple.
Definition 11 (Submodularity) A set function g 2 R is submodular, for every A ACBSS and E S \ B holds that
g (AU ((A) 2 (BU gB
Lemma 12 Increasing the input budget of Algorithm Zawways leads to no worse output. Formally, denote the output of Algorithm ass S,, and Sy under different input budgets b and V. For any budget pair >> b, we must have either Sy = Sb or g(Sw) ) > g(%))
Proof of Lemma of Algorithm 2
12 Considering two input budget b and b' and the corresponding outputs So and Sy In the following, we show that g(Sb:) 2 g(S)) if > b. Without loss of generality, inn E 2 and Sy {Ki, k2,
denote S (ji,
km } 2 the corresponding
output, where S (1,2, ... ,N)....,,,,.................., S n S N, 1 S m S N.
Under different budget. the selected client in each round can vary due to the changed constraint in Line of Algorithm 2 For example, under budget b, client with the largest ratio may not be selected because including it would cause the total cost to exceed b. In contrast, under budget V' it can be selected due to the increased budget. Consequently, this can create different output sequences S, and Sy-
Let be the first time when the two sequences diverge, i.e, ji hig VI S <i<+ T, and j. * ky. If such a r does not exist, the two sequences are precisely the same and we will have Sy. = Sb. In the remainder of this proof, we assume T exists and show that g(Sw) ((S)) consequently. Let S7 and Sj be the set that contains the first r elements in S₁, and Sv, so we have S S According to the greedy strategy (Line 3 of Algorithm 2 it is clear that Dr. > Ei=r Dj. meaning that the cost of client , is even higher than the total costs of clients in S S. which is the reason that k appears in the output Sy under larger budget 1/ but is not (thus is skipped) in the output S, under Moreover, this also implies that client ki has a larger co-sst ratio than that of any client in So \ ST-1 at the 7-th round, formally
g(S U (k+)) 9(S g(5 u (ii)) 9(5 Vi [T,n]
(8)
DR-
Dj.
For clarity, we denote the value of client k, as (lk,11771) = 9(S) (k+}) fying how much client k; can improve the objective function with respect to the set S we have
g(S ) quanti-
Then
Dj ((A 1 D,. S
((kk De. - u(Ni|ST
Σ
Dj.
Der
De.
where the first inequality follows from Eq. 8 and the second one holds true because Dr. > Ei_r Dj.. Therefore, we derive that
(9)
Now are ready to compare the objective value of S, and Sor, and show that g(Sw) > g(Sb). By simple decomposition, we can rewrite g(S)) as follows
g( (()) = g( [ji.ja
= g(0) + (o((ii)) - ((0) + (o(fii - e(i)) ( .... (g(S)) g(S,) \ (1-1)
g(0) + (( +(22(()) +... + si
= =00)= + Σ u(j 1 + Σ wGbls
13

---

Published as a conference paper at ICLR 2024
Likewise, we have
9(5b) 9(0) Σ (k(ils + Σ v (kkp15g
p=
Recall that j, = ki Vi < T, and thus we have viils = u (ki 1S Vi Therefore,
g(Sur) - g(Sb) Σ uk::sst Σ
-(ilst
uk-r1s +
Σ (1t:1))))) Σ (H1s
1=++1
(ilss ))+
Σ okkis
Σ -i -
0
where the first inequality directly follows Eq. 9 and the last step utilizes the submodularity prop- erty (see Definition of the submodular function g. i... v( > -(i,1s ), > 7. This concludes the proof.
Now we are ready to prove the monotonicity of Algorithm by contradiction.
Proof of Proposition 5 An algorithm is monotone if a client a remains selected by the algorithm
whenever its reported cost satisfies D' D... provided it gets selected when reporting D... Let
= {t1, b2 ..,,,n } and b be the resulting participant set and budget determined by Algorithm when client a reports Da. Without loss of generality, we set a = ig. where S. k S n, and denote S = {ú,, ig.... 2 as the set of clients selected before a. According the greedy selection strategy in Algorithm 2 we have
g(St-1) 9(Sh-1 U (i)) - g(S
VWESSS D.+ Σ 5D (10) JES
D.
D.
Denote S' and b' as the resulting participant set and budget determined by Algorithm when client reports D' a D... Since decreasing client a's 's claimed cost will increase the ratio in the left- hand side of Eq. (TO), will remain selected (no later than the k-th round) when &' S b, otherwise the terminating participant set Sy is not sufficient. The algorithm only deviates from this when the following condition is true:
g(S* 1 U {a+) 9(8h-1) g(S U (i)) - -(S
Ei EE St D, + ΣD, SS
D'a
JESK-1
According to Eq. 11). this is only possible when 6' because the increased budget allows addi- tional candidate chients with both larger value and cost, potentially surpassing the largest affordable ratio under However, it contradicts the fact that any feasible terminating budget must be at most b- as Lemma [2 guarantees that a larger budget input to Algorithm 2 must always result in either exactly the same set or different set with strictly higher objective value. Meanwhile, the terminat- ing condition (Line 3 of Algorithm|] I] ensures that the entire search process will promptly terminate once it finds the minimum budget that satisfies the constraint. Therefore, given budget b already sat- isfies the constraint, it is impossible for the algorithm to terminate with a solution that has higher budget than b, which finishes the proof.
B GREEDY INCENTIVE SEARCH
In contrast to Algorithm I one straightforward alternative is to adopt the vanilla greedy method to solve the problem in Eq. (3. as presented in Algorithm 3 The idea is iteratively rank all non- selected clients according to their individual value-to-cost ratio and choose the one with the largest ratio (Line 3-4), until the resulting participant set satisfies the constraint (Line 2).
14

---

Published as a conference paper at ICLR 2024
Algorithm 3 Vanilla Greedy Incentive Search
1: S; + 0, = {1. 2, ..
2: while (S,) log 3 do
3: f Largg max J.3 ((( D3
4: + (
5: return S.
not difficult verify this straightforward greedy algorithm also monotonic, as decreasing a client's claimed cost essentially encourages its selection, thus making it truthful mechanism. One notable difference between this greedy incentive search algorithm and truthful incentive search (Algorithm T is that it does not compromise for the constraint. As a result, as pointed out by previous studies (Wolsey) 1982). this greedy algorithm does not admit any constant-factor approximation guarantee (i.e., it becomes problem instance specific), as shown in Lemma 13
Lemma 13 (Theorem 2 of Wolsey (1822) Under parameter B and clients' reported participation
cost Dj = (Di,s"' ... xN,,). Algorithm is guaranteed to obtain a participant set S. such that
Σ D.. $ (1 In min )2})
Σ Di. and ge(Ss) 2 log
iES
:ESt
in which A1 max 9: a=((())-ac(0) 9. (s( (e()
9.(S U (1)) (((S)) 0} where the denominator
i,k
the smallest non-zero marginal gain from adding any element E Š the intermediate set Sk. iee. the set contains the first k elements of the output set St, and the numerator is the largest where K is the total number of iterations the greedy search and .x
singleton value of 9: X2
ok = max ((()" A3 a(S)
g(5)-9(0)
D..
Alternatively, we reformulate Algorithm into an equivalent counterpart (Algorithm 4 that provides a bi-criteria approximation guarantee similar to Algorithm [ Note that these two variants essentially lead to the same outcome when parameterized with 81 g(1- 1) and 32 3, where 31 and B2 are the specified apper-parameters in Algorithm and Algorithm respectively.
Algorithm 4 Greedy Incentive Search (V2)
Algorithm 5 ORDEREDBUDGET
Require: 8, = 2 N
Require: 5 -1,,
1: B < ORDEREDBUDGET
1: S. < 0, B
2: S; b+ 0, k
2: while S S + 0
3: while (s.) < (1 -
log do
9e ((..))))))))
3:
arg JEX
4: + b+ B[k]
D5.,
4: S
5: GREEDY
5: B+ BU Bu
6:
k- ++1+1
7:
return St
6: return B
Lemma Under parameter 3 and clients' reported participation cost D. = (Br,, r.. DN... Algorithm 4 provides bi-criteria approximation such that
Σ Dr S max D. + EDe, and ge(St) 2 - (1- logg3
LES.
iES;
where S, is the output of Algorithm 7 and St is the ground-truth optimizer of problem defined in Eq. 77.
Proof of Lemma 14 The proof of this lemma largely repeats that of Lemma 9 with a minor differ-
ence in Eq. 7 (i.e.. b = (1 e)b vs., b b' + B(k)) Unlike Algorithm slightly increasing the
15

---

Published as a conference paper at ICLR 2024
budget by constant factor (1+ c), Algorithm increases the budget in pre-ordered way based on Similar to Eq. 7 the subscript omitted, and we have
result Algorithm 5
Σ iESp
Dbsb- Blk S max D
Σ
D:
(11)
iES*
Additionally, it is not difficult gu (S)) > (1-e-1) log since this is the terminating condition of Algorithm 4
Combining both completes the proof.
C TECHNICAL LEMMAS
Lemma (Lemma 10 of Abbasi- Yadasi- al. (2011) Suppose X1, x2, E IRd and for any S t, ||x||2 L. Let V, AI + Ex= x,X, for some X 0. Then,
det(V,) s (A +A+ (T.2/a)
Lemma 16 (Lemma 11 Abbasi- et al. (2011) Let (Xt) be sequence in Rd. V is a d positive definite matrix and define V, V E. X,X1 T.X! Then we have that
det (Vn) del(V)
7
log
Further, if Xell2 S for all i, then
min 1, [| } s (log det (V.) - log det V) $ 2 (dlog ([trace(V)+ + nI²) /d) log det V).
D PROOF OF LEMMA 7
Our proof utilizes the following matrix determinant lemma (Harville 2008).
Lemma 17 (Matrix Determinant Lemma) Let A E Raxn be an invertible n-by-n matrix, and B, B.C E Raxx are n-by-m matrices, we have that
dct(A + BCT) = det(A) det + CT A-)
Proof of Lemmal 7 known that the infinite critical value unavoidable for monopoly client under the truthful mechanism design. To eliminate this issue, we first analyze the root cause of the existence of monopoly client. Denote V. as the covariance matrix constructed by all sufficient statistics available in the system time step t, and AV,, = X,, Xn. Xn E A Specifically, client i is monopoly, i.e., being essential to satisfy the constraint in Eq. (3) at time step i, such that having the other N clients' data still cannot satisfy the constraint. According Lemma 17 plugging in V AV,, and = = XT we have
det AV..)
det(V))
det X., AV.
where AV. XT e A At represents the number of new data points in AV.. Next, show that there exists lower bound of the ratio above, such that as long parameter 3 less than the lower bound, it guaranteed that no client can be essential. Moreover, for
the hyper-
a positive definite matrix A E dxd
we have A-1
Xmmmtaj where Amin (A) denotes the minimum
eigenvalue Plugging in A -AV,, we have (Vr AV..) &
Amta (V. AV..) $ X
16

---

Published as a conference paper at ICLR 2024
where À > is the regularization parameter defined in Eq. 12 It follows that
1
det(Iar (V, AV,,))
det(lar + {
A det(ALa + AVi,)
det(Ta + x Xn)
da
dei(V,, + Ala)
d N (A (L+123/ (1 (1+
where the second step holds by elementary algebra, the third step utilizes the fact that Vi, & AVi, and the last step follows from Lemma 15 Therefore, as long as we set I (1 + tT? /Ad) guaranteed that no client will be essential at time step f. This finishes the proof.
E COMMUNICATION COST AND REGRET ANALYSIS
As TRUTH-FEDBALT directly inherits from the basic protocol proposed in (Wei et al. 2023) with truthful incentive mechanism, most part of the proof for communication cost and regret analysis (Theorem 4) in their paper extends to our problem setting. Therefore, with slight modifications, we can achieve the same sub-linear guarantee.
In essence, the only difference in terms of establishing the theoretical bounds for regret and com- munication cost between our method and (Wei et al., (023) lies in the relaxation of the constraint Eq. (3), which deviated from the original constraint Eq. (1) by a constant- factor gap of (1- (1-e-1)
2 ()) into log de- (S)) 2 (1) log (), the notion of 33 in our work is slightly different from that in their work. Specifically, denote the hyper-panne prper-parameter in their method as B. then any used their theoretical results can be replaced by our notation via the trans- formation 3 = 31-
Moreover, as we reformulate the determinant ratio constraint (i.e., (Vs()) de)((),.(S))
terminant ratio constraint (i.e., log (St
In the following, present the corresponding theoretical results of our proposed TRUTH-FEDBAN and refer the readers to the proof details in Theorem 4 of (Wei al. 2023).
Lemma 18 (Communication Frequency Bound) By setling the communication threshold D.
T No by
(1-e /
T2 NodRlogT log 3, the total number of communication rounds is upper bounded
P = O(Nllog))
where R= [dlog1 x2) = O(dlog
Communication Cost: In each communication round, all clients first upload ((P) scalars the server and then download ( scalars. According to Lemma 18 the total communication cost is CT = P. O(Nd²) = 2 T).
Lemma 19 (Instantaneous Regret Bound) Given parameter 3, with probability 1 - 8, the instan- taneous pseudo-regret ri (0*, x* - -xx) in j-th communication round is bounded by
T dlog z
det(Vg.2,)
rt 0 0
||xe||l/: 3(---1
det(V
We followed the notion of good epoch and bad epoch defined in (Wang et al., 2020). Combining with Lemma 16 we can bound the accumulative regret in the good epochs as,
Proof of Theorem 10
REG REGgood= =o =0
( d
T log 5 logg
/T
17

---

Published as a conference paper at ICLR 2024
Furthermore, we can show that the regret across all bad epochs satisfies,
REGbad O [dds De log
T
log
Using the communication threshold D.
T
(1 e e
N log log 3 specified in
T
N-dlogT
Lemma 18 we have
Rr R.EEE good + REGbad
(VOL d
= Henceforth, by setting g e k, we can show that therefore
VBL-o- VTlogT +0 Nd No
log..T. T.
T
log 1 Ndlog T 31-0-1
T
N'
T
Nalog? log
gi-0 and
No
RT R /
(
d V V + +0 + - OddTTlog))
This concludes the proof.
F GENERAL FRAMEWORK FOR INCENTIVIZED FEDERATED BANDITS
Algorithm Incentivized Communication for Federated Linear Bandits
Require: De 0. D. (DI.,.... DD..... o, > 0, (0, 1)
1: Initialize: [Server] Vi = Odxd E Rdxd 6y.0 = 0₂ E Rd
2:
AV 1.0 = 0 Odxd: Ab_ 1,0 0g. Vj E [N]
3:
[All clients] V4,0
Oaxd, 0i,0 Og, AV.. Odx Abs,o Od, A4.,0 = 0, [N]
4: for f= 1,2, 7.. do
5:
[Client i,] Observe arm set Ar
6:
[Client i,] Select arm X; E Ai by Eq. 12 and observe reward
7:
[Client 4,] Update: Vn,t += X,X, biatt XtI/i AVe.t += x,X, Ab t += l/. Atie, +=
8:
9:
if Ati, log det(Vi AV,, D. then
[All clients + Server] Upload AV,,, and let S f1. ,N] [Server] Select incentivized participants S, = M(, D Incentive Mechanism for E S, do
11:
12:
13:
[Participant i - Server] Upload Abs
14:
[Server] Update: Vg. += AV, by.t Abú
15:
AV-j.t j.t += A AV.. Ab-j,t += Ab;,, #i
16:
[Participant i] Update: AV, 0. Abi, 0, Ati, =0 for vi E [N] do
18:
[Server - All Clients] Download AV i.f Ab-it
[Client i] Update: Vi, += AV i.t. bú, += Ab Ab_i.
20:
[Server] Update: AV = 0, Ab-it 0
Algorihtm 6 shows the incentivized communication protocol proposed by Wei et (2023). The arm selection strategy for client i, as time step is based on the upper confidence bound method:
X1 arg max x Oi,,t-(()) + - (1 xeA,
(12)
where 0 Ve (A)o,, is the ridge regression estimator of 0, with regularization parameter A > 0, (i,+t1(A) = V and a4,t-1 = / log (A) denotes the covariance matrix constructed using the data available client up time
det( det(V,,.t= log 1/8+ VA.
det (X7)
18

---

Published as a conference paper at ICLR 2024
G IMPLEMENTATION DETAILS
G.1 HYPER-PARAMETER PARAMETER SETTINGS
As introduced in Section the proposed TRUTH-FEDBAN works with any realization of the valu- ation function. For demonstration purpose, we instantiate it as a combination of client's ' weighted data collection cost plus its intrinsic preference cost, i.e., f(AV..)
w det(AVi.e) + C.. where w 10-4, and each client i's intrinsic preference cost C; is uniformly sampled from (0, 100). In the simulated environment (Section 5 the time horizon is 6250, total number of clients c = 1.0, 3 = 0.5 in Algorithm and Algorithm The tolerance factor Algorithm is 1.0.
N = 25, context dimension d = 5. We set the
As stated in Section 4.2 we do not assume a monopoly-fiee environment and thus any truthful incentive mechanism has to pay essential clients infinite incentives guarantee their participation when necessary. Nonetheless, to visualize the impact of infinite payment, we simplify it as a constant value of 1 that is orders of magnitude greater than the average participation cost. and the infinite critical value is simplified.
G.2 CRITICAL VALUE CALCULATION FOR ALGORIHTME 3
It is not difficult to show that Algorithm 3 is also monotone and thus inherently associated with critical payment scheme to make the resulting mechanism truthful. We now elaborate on the critical value calculation method for it. And the critical value based payment scheme for Algorithm can be derived in a similar spirit.
For each client a E S in the participant set S (subscript is omitted for simplicity), the critical value Co is determined follows. First, rerun Algorithm 3 without client a, i.c., setting Š' S {a}; the process fails to terminate with a feasible set S it suggests that client a is essential to satisfy the constraint, then its critical value is ca co. Otherwise, the process can terminate and return feasible set, denoted as {ūr, (2, ... .ik) then the critical value ca calculated by
Ca max Dr, 9(S -(5))))((5)))) kE[R]
(13)
- 9(
where is and S% represent the selected client and intermediate set of 5' at k-th round. Denote v(a(Sh_1) = g(5 U {a]) - g(5%_1), now suppose we are placing client a at the k-th po- sition of S'. To do so, the maximal participation cost that client a can claim should satisfy that the corresponding value-to-cost ratio is higher than that of client ik, i.e., 1))DD Z other words, the maximal cost client a can claim to replace is is D. D. / Therefore, the critical value Ca calculated in Eq. 13 ensures that as long as the client a claims slightly less than ca. it can replace at least one client in the K rounds, thus becomes selected by the server. On the contrary, if D, is higher than Ca. we can show that will by no means get selected by the server. Specifically, the condition D,, > Ca guarantees o18t_,1(i..)-9((5...) Ak [K]. We can start from the selection of the Du
9(S% ((a)) -aa))-((((5... 9(S(_1)
Do first client = 1, and we want to guarantee client will not be selected. The condition tells us gla) < g(11) where i denotes the client that was selected in the first place when we exclude a.
D.
D.
We know glin) is also higher than all the other clients, so algorithm will still select client in. i.e., D.,
S {ii} = St. Then for l = 2, the condition suggests ((a))(()))g(S)) [(t))(a))-((5)) D.
D.
((8( = )(S, Therefore, a will not be selected at k. = 2 either, and Dig
S2 = =yy We can show client a will not be selected in S by induction.
G.3 CRITICAL VALUE CALCULATION FOR ALGORIHTM 1
In contrast, there is no explicit formula to calculate the critical value in TRUTH-FEDBAN. Follow- ing Mu' Alem & Nisan (2008), we calculate the critical value using bisection search as described in Algorithm]
19

---

Published as a conference paper at ICLR 2024
Algorithm 7 Critical Value Calculation (Bisection Search)
Require: == (1, ,N,, Dr = {D1,e, De -. DN.h. incentive mechanism M, concerned client i, budget 6, tolerance 7
1: Initialization: L +- 0, H <-
2: while -- 2 do
3: Calculate critical value: 6 f L+-
2
4: Update D: Dia & Gi.
5: Run incentive mechanism: S MM5: D)
Algorithm
6:
if i E S then
7:
L G
8:
else
9:
H 4 Ci.t
10:
Return client i's critical value Ci
The idea remains the same as stated above, to calculate the critical value of a particular client, we first rerun Algorithm T without it in the candidate client set. If the client is essential, its critical value is Gi = bo. Otherwise, we can calculate the critical value via Algorithm 7 Specifically, for any participant in the set St found by Algorithm []] it is clear that the bound of critical value is its claimed cost Di.e. otherwise it would not have been included in S₁. Denote b the terminating budget determined by Algorithm| [ when client is not considered, we can also have a upper bound for C3.t S b. With the lower and upper bound input to Algorithm it has been proven (Burden et al. 2015) that the number of iterations that Algorithm needs to converge to root to within certain tolerance is bounded by [logz ?9 )7, where " =Tb-
H TIME COMPLEXITY ANALYSIS OF ALGORITHM
As the proposed Algorithm T includes a subroutine process of Algorithm thus we start the time complexity analysis with Algorithm / Specifically, the worst-case time complexity of the while loop is (NN). The operation inside the while loop involves finding the maximum element in set, which takes O(N) time. Therefore, the time complexity of Algorithm 2 O(N)).
Let M be the number of iterations of the while loop (Line 3) Algorithm [ Hence, the time complexity of Algorithm [ is O(M N2). Specifically, the worst case to consistently in- crease the budget until it reaches Σ Di,.. Therefore, we can upper bound by considering the loop-breaking case: by (1 + c)M 2 ΣN Dr,. i.e. M S logi+e (E D.. 60 ), where
bo minies Di.t- As result, Algorithm yields the following polynomial time complexity of Dea)
O( logite EEm bo N2).
20


Reviews:
[{"review_id": "Q7cjk3BiZE", "reviewer": "Reviewer_1gFC", "summary": "The paper studies the problem of learning the unknown parameter in linear parametric bandits via federated/distributed learning (FL) with a central server and multiple clients, when each client must be incentivised to participate in the learning task. More specifically, each client possesses an intrinsic participation cost (e.g., amount of local computational resources at the client required to execute its share of the FL task), and participates only when its incentive for participation exceeds its participation cost. The paper studies the interesting and practically relevant setting when each client may potentially misreport its participation cost (in the interest of exploiting the system or maximising its utility), a setting that is not studied in the prior works. The authors borrow the ideas of *truthfulness* and *social cost* (popular in economics) to design an FL algorithm in which each client can maximise its utility only if it reports the true participating cost. For such an algorithm, the authors obtain bounds on the communication cost and pseudo-regret for FL with incentivised communication, while also demonstrating that the optimal social cost may be achieved up to scaling factors.", "questions": "I have discussed the questions under \"Weaknesses\".", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper studies the interesting and practically relevant setting when each client may potentially misreport its participation cost (in the interest of exploiting the system or maximising its utility), a setting that is not studied in the prior works. For the problem of FL with incentivisation studied in the prior work of Wei et al. (2023), the paper brings in the ideas of *truthfulness* and *social cost* from economics to quantify the performance of a regret-minimisation algorithm. A formal demonstration of the monotonicity of Algorithm 1 is one of the key contributions of the paper; a similar result is missing in the prior works on FL. The experimental valuations are adequate and insightful.", "weaknesses": "1. The regret analysis seems to follow quite straightforwardly from Wei et al. (2023) with slight modifications in the hyper-parameter values (as indeed noted on page 17 of the supplementary material, in the description trailing Lemma 18). Therefore, it appears that there is not much novelty in the regret analysis, leaving the novelty to the demonstration of truthfulness and near-optimality of social cost. \n\n2. In continuation to the last sentence of the previous point, there appears to be no motivation to study the criterion delineated in (1). The authors simply proceed to analyse the objective function in (1), simply because it appears in Wei et al. (2023). No further explanation of the criterion in (1) or of its relevance to FL is provided in the paper.\n\n3. The authors consider a very specific form for the valuation function $f(\\Delta V_{i,t})$ without motivating the same. Has a similar valuation function been studied in the context of FL? More generally, what conditions must $f$ satisfy for the analyses to go through? These are not discussed in the paper. \n\n4. On the algorithmic side, the authors prove in Lemma 6 that if the selection rule (a rule for selecting a set $S_t$ of clients that would participate in the FL task at time $t$) can be computed in polynomial time, then so can the critical value associated with the selection rule. However, no explicit result stating how much time is taken by Algorithm 1/2 to compute the selection rule is provided in the paper. While the authors provide an explicit scheme to compute the critical value, the authors do not explicitly prove that their Algorithm 1/2 computes the selection rule in polynomial time. \n\n5. The statement of Lemma 7 appears to be contradictory to one of the statements made in its proof (presented in Appendix D). In the proof, the authors identify that $\\left(1+\\frac{t L^2}{\\lambda d} \\right)^{-d}$ is a lower bound on a certain ratio of determinants, and further note that \"if the hyper-parameter $\\beta$ is **greater** than the (preceding) lower bound, it is guaranteed that no client can be essential\". However, Lemma 7 states the contrary. Furthermore, the constants $L$ and $\\lambda$ appearing in the statement of Lemma 7 are not defined in the main text.\n\n6. There are no comments on the tightness of the bounds on the communication cost and pseudo-regret in relation to the bounds appearing in the work of Wei et al. (2023) (the key piece of work the current paper seems to be based upon). In the process of achieving near-optimal social cost, what is the impact on the communication cost / number of rounds of communication and regret? A formal comparison along these lines with Wei et al. (2023) is missing.\n\n7. Immediately following the statement of Lemma 18 in Appendix E, the authors state that \"In each communication round, **all** the clients upload $O(d^2)$ scalars to the server and then download $O(d^2)$ scalars.\" Why do **all** the clients participate in the communication and not just the ones from the selection set $S_t$ at the communication time instant $t$? This is a little confusing, and not discussed elsewhere in the paper.\n\nThe writing of the paper can be significantly improved. \n\n1. The *incentive* $\\mathcal{I}_{i,t}$ introduced in (2) does not appear to be used elsewhere in the paper. \n2. In Definition 4: $c\\_{i}(\\mathcal{M}, \\widehat{D}\\_{-i, t}) \\to c\\_{i, t}(\\mathcal{M}, \\widehat{D}\\_{-i, t})$.\n3. In the paragraph before Lemma 6: \"Lemma 5\" should be replaced with \"Proposition 5\".\n4. In the proof of Theorem 8: $i \\notin S\\_t \\to i \\notin S\\_t^\\prime$.\n5. The notion of \"communication threshold\" in Theorem 10 is not explained in the paper.\n\nThe paper is generally missing the overall feel of an FL paper (no details about the communication protocol, which set of clients participate in communication, what information is communicated from the clients to the server), and seems to only build upon the setting and results of Wei et al. (2023) on the social cost and truthfulness aspects.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "XkkO8FeGbm", "reviewer": "Reviewer_ihns", "summary": "The paper studies a federated learning problem with N strategic, individually rational agents that repeatedly interact with an environment over T rounds to receive rewards. Every agent faces the same environment characterized by a common latent parameter and stochastic rewards that are linear in the action with additive zero mean sub-Gaussian noise. Each agent wants to minimize her regret over the T rounds of interaction, subject to communication costs. The authors propose a truthful mechanism that incentivizes agents via payments (by a central server) to communicate and report their true participation costs, and simultaneously guarantees $\\tilde{\\mathcal{O}}\\left( \\sqrt{T} \\right)$ individual regret.", "questions": "Is the bi-criteria approximation in Theorem 9 best possible or it can possibly be improved to $[1+\\epsilon, 1-\\delta(\\epsilon)]$, where $\\delta(\\epsilon)$ decreases in $\\epsilon$ with $\\delta(\\infty) = 0$. Also, is $\\delta(0) = \\frac{1}{e}$ best possible?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The main contribution, in my assessment, is an improvement over Wei et al. (2023) in proposing a truthful incentive mechanism (for reporting participation costs) that simultaneously guarantees $\\tilde{\\mathcal{O}}\\left( \\sqrt{T} \\right)$ near-optimal learning loss.", "weaknesses": "Given that this work is based off of the model of Wei et al. (2023) who essentially formulate all of the problem setting and the optimization problem being solved, the contributions could run the risk of being seen as incremental. \n\nHowever, I believe this paper provides an improved and richer solution concept in comparison to that proposed in Wei et al. (2023) by factoring in regret, social cost and as well as the incentives involved in reporting participation costs.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "q6BiaW5yKs", "reviewer": "Reviewer_3EFN", "summary": "The work builds on, as an extension of Wei et al. (2023), to incentivize the truthful participation of clients to improve overall utility for each client. The authors show the developed communication protocol TRUTH-FEDBAN enjoys near-optimal theoretical guarantees on regret and communication costs.", "questions": "Please consider the questions raised in the weakness section.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "This work presents a mechanism design to ensure the truthful participation of clients, where the client's only beneficial strategy is to share their true costs in a federated bandit learning setting. The incentive-compatible communication protocol offers near-optimal theoretical guarantees on regret and communication costs. Numerical evaluations validate the method's efficacy.", "weaknesses": "1. I am a bit unsure of the contribution and the motivation for the developed solution of this work, particularly considering how this work is built (as an extension) on Wei et al. (2023); hence, the claim for making this work a first attempt in mechanism design for federated bandit learning seems incorrect? Also, for the method developed, several recent works on federated settings, such as FL, tackle such issues for truthful and fair participation, employing economic tools. Contract Theory-based methods or Auction-based methods have been \"extensively\" employed in mechanism design for truthful interaction between the clients and the server. For instance, [R1, R2]. \n\n[R1] Karimireddy, Sai Praneeth, Wenshuo Guo, and Michael I. Jordan. \"Mechanisms that incentivize data sharing in federated learning.\" arXiv preprint arXiv:2207.04557 (2022).\n[R1] T. H. Thi Le et al., \"An Incentive Mechanism for Federated Learning in Wireless Cellular Networks: An Auction Approach,\" in IEEE Transactions on Wireless Communications, vol. 20, no. 8, pp. 4874-4887, Aug. 2021, doi: 10.1109/TWC.2021.3062708\n\nIn that reference, I am not sure relaxing the data sharing cost with a valuation function, commonly used in standard economic analysis, is a sufficient contribution to this work. Can you explain more about the missing guarantees on the social cost of Wei et al. (2023)? Later, after Def. 2, you mentioned the definition of social cost in this work is different than theirs.\n\n2. Following my earlier comment, the setup and the interaction procedure is unclear to establish the contribution, again, as compared to Wei et. al., 2023. The preliminary model is not rigorous to that end. For instance, what exactly is pulling the arm characterised in Section 3 in a federated bandit setting? How to interpret y_t following it? what is w in footnote 1? and so on. This can be significantly improved.\n\n3. Can the authors support the claim that \"more frequent communication leads to lower regret\"? (and the line that follows in pg. 3) It is understandable in terms of the communication overhead, but this is also the fact that you gain in training efficiency. This leads back to my earlier confusion regarding how \"regret\" is quantified.\n\n4. Is the critical value defined in Def. 4 unique?\n5. I must admit the proof of monotonicity has not been conveyed clearly in its current form; can you provide a discussion on this?\n6. Simulations:\n- The methods build on Wei et. al. 2023 but didn't use it as a baseline.\n- What about the time-complexity analysis and the overall learning performance following the proposed approach? Also, how well the method scales.\n- The general setup with \"sequential interaction\" is limiting in itself, in my understanding.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "quekXUhdk1", "reviewer": "Reviewer_Jfq6", "summary": "This paper extends the recent work on incentivized linear federated bandits (Wei et al. 2023) to one where the clients’ communication costs are unknown, and the server must devise a mechanism for payments that is incentive-compatible. The authors use ideas from mechanism design to design such a scheme while keeping the total payments small.", "questions": "- A client’s utility, $u_{it}$ was not defined, so truthfulness (definition 1) is not well defined. Does a client’s utility involve both the regret as well as the payment? If so, how are these combined?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Novel setting that combines multi-armed bandits with mechanism design \n- Theoretical results seem correct and non-trivial \n- I appreciate the numerical simulations that were conducted to corroborate theory", "weaknesses": "I find the main weakness of this paper to be the model. It is a very complex model that combines many different aspects (linear bandits, multiple clients, communication cost, incentivizing payments, truthfulness). The paper did not provide any motivating application for studying this complex model.\n\nRegarding the motivation for the model, one of my main points of confusion is in how the reward/regret of the bandit algorithm can be compared to the incentive payment paid out by the server. Relatedly, what incentive does the server have, to pay the clients (out of pocket) to get them to participate? From my understanding, it is each client that is performing some action, and hence it is in the client’s best interest that the bandit algorithm chooses the best actions. Now, federated learning will improve the learning algorithm since more data is collected, so it is in the agent’s best interest to participate in federated learning. If the “communication cost” is higher than the benefits of participating in federated learning, then the agent can simply choose not to participate. In this paper, the server will pay such a client to participate - but what benefit does the server get when the agent participates? What if the true “communication costs” are exorbitant (e.g. $1M per communication)? The algorithm in this paper still makes the server pay, regardless of the scale of these costs. \n\nIf one is considering the problem in this paper purely for theoretical interest, the fact that the model was so complex makes it difficult to identify how the results contribute to the theory of multi-armed bandits. Most of the paper was about mechanism design, but it took a long time for me to understand the underlying federated linear bandit model - and it wasn’t clear to me which parts of the underlying bandit model were crucial and which were not.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)