A Simple and Provably Efficient Algorithm for Asynchronous Federated Contextual Linear Bandits
Authors: Jiafan He
Tianhao Wang
Yifei Min
Quanquan Gu
Venue: NeurIPS 2022 Accept (2022)
Keywords: linear bandits
federated learning

Abstract: We study federated contextual linear bandits, where $M$ agents cooperate with each other to solve a global contextual linear bandit problem with the help of a central server. We consider the asynchronous setting, where all agents work independently and the communication between one agent and the server will not trigger other agents' communication. We propose a simple algorithm named FedLinUCB based on the principle of optimism. We prove that the regret of FedLinUCB is bounded by $\widetilde{\mathcal{O}}(d\sqrt{\sum_{m=1}^M T_m})$ and the communication complexity is $\widetilde{O}(dM^2)$, where $d$ is the dimension of the contextual vector and $T_m$ is the total number of interactions with the environment by agent $m$. To the best of our knowledge, this is the first provably efficient algorithm that allows fully asynchronous communication for federated linear bandits, while achieving the same regret guarantee as in the single-agent setting. 

A Simple and Provably Efficient Algorithm for Asynchronous Federated Contextual Linear Bandits
Jiafan He
Tianhao Wang"
Department of Computer Science University of California Los Angeles
Department of Statistics and Data Science
Yale University
Los Angeles, CA 90095 Siafanhee9@ucla
New Haven, CT 06511
tianhao. wang8yale edu
Yifei Min
Quanquan Gu
Department of Statistics and Data Science Yale University
Department of Computer Science University of Californa, Los Angeles
New Haven, CT 06511 yifei min@yale... edu
Los Angeles, CA 90095 gguêcs wuw..ccacceo edu
Abstract
We study federated contextual linear bandits, where M agents cooperate with each other to solve global contextual linear bandit problem with the help of central server. We consider the asynchronous setting, where agents work independently and the communication between one agent and the server will not trigger other agents' communication. We propose a simple algorithm named FedLinUCB based the principle of optimism. We prove that the regret of FedLinUCB is bounded by Oldy) Σ =m== Tm) and the communication complexity (dd?), where d is the dimension the contextual vector and T,, is the total number interactions with the environment by m-th agent. To the best of our knowledge, this is the first provably efficient algorithm that allows fully asynchronous communication for federated contextual linear bandits, while achieving the same regret guarantee in the single-agent setting.
1 Introduction
Contextual linear bandit is a canonical model in sequential decision making with partial information feedback that has found vast applications in real-world domains such recommendation systems (Li
et al. 2010a by Gentile et al. 20144 Li et al. 2020). clinical trials (Wang 1991 Durand et al. 2018
and economics (Jagadcesan al. 2021
al. 2022). Most existing works on contextual linear
bandits focus on either the single-agent setting (Auer 2002; Abe et al. 2003 Dani et al. 2008
Li al. 2010a Rusmevichientong and Tsitsiklis 2010 Chu et al.) 201 Abbasi- Yadkori al.
201 Agrawal and Goyal, 2013) or multi-agent settings where communications between agents
instant and unrestricted (Cesa-Bianchi al., 2013] Li et al.. 2016) Wu et al. 2016] Li al.
2021). Due to the increasing amount of data being distributed across large number of local agents
(e.g.. clients, users, edge devices), federated learning (McMahan et al. 2017 Karimireddy al.
2020) has become an emerging paradigm for distributed machine learning. where agents can jointly learn global model without sharing their own localized data. This motivates the development of distributedd/fcderated linear bandits (Wang et al. 2019; Huang al. 2021 Li and Wang 2022a), which enables a collection of agents to cooperate with each other to solve a global linear bandit
Equual contribution.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

problem while enjoying performance guarantees comparable to those in the classical single- centralized setting.
However, most existing federated linear bandits algorithms are limited to the synchronous set- ting (Wang al. 2019 Dubey and Pentland 2020; Huang et al. 202T), where all the agents have to first upload their local data to the server upon the request of the server, and the agents will download the latest data from the server after all uploads are complete. This requires full participation of the agents and global synchronization mandated by the server, which is impractical in many real-world application scenarios. The only notable exception is and Wang (022a), where an asynchronous federated linear bandit algorithm is proposed. Nevertheless, in their algorithm, the upload by one agent may trigger the download from the server to all other agents. Therefore, the communications between different agents and the server are not totally independent. Moreover, they make a stringent regularity assumption on the contexts, which basically requires the contexts to be stochastic rather than adversarial as in standard contextual linear bandits. That said, their theoretical proof is actu- ally flawed as they ignored some unique challenges caused by asynchronous communication (see Appendix A. for details). Therefore, how to design a truly asynchronous contextual linear bandit algorithm remains an open problem.
In this work, we resolve the above open problem by proposing a simple algorithm for asynchronous federated contextual linear bandits over star-shaped communication network. Our algorithm is based on the principle of optimism (Abbasi- Yadkori et al. 2011) and enjoys the following advantages: (i) Each agent can decide whether or not to participate in each round. Full participation is not required, thus it allows temporarily offline agents. This is much more flexible than existing algorithms for federated linear bandits in WWan et al.) (2019) Dubey and Pentland| (2020); Huang et al. (202T) where all agents are required to participate in each round; and (ii) the communication between each agent and the server is asynchronous and totally independent of other agents. There is no need of global synchronization or mandatory coordination by the server, in contrast to Li and Wang (2022a) where each agent might be asked by the server to download data. In particular, the communication between the agent and the server is triggered by matrix determinant-basee criterion that can be computed independently by each agent. Our algorithm design not only allows the agents to independently operate and synchronize with the server, but also ensures low communication complexity (i.e., total number of rounds of communication between agents and the server) and low switching cost (i.c., total number of local model updates for all agents) (Abbasi-
et al. 2011).
While being simple, our algorithm design introduces a challenge in the regret analysis. Since the order of the interaction between the agent and the environment is not fixed, standard martingale-based concentration inequality cannot be directly applied. Specifically, this challenge arises due to the mismatch between the partial data information collected by the central server and the true order of the data generated from the interaction with the environment, as is explained in detail in Section and illustrated by Figure | We address this challenge by novel proof technique, which first establishes the local concentration of cach agent's s data and then relates it to the "virtual" global concentration of all data via the determinant-bart based criterion. Based this proof technique, are able to obtain tight enough confidence bounds that lead to a nearly optimal regret. Moreover, our theoretical analysis relies only on minimal assumptions that standard for contextual linear bandits, relaxing the strong assumptions made in Li and Wang 2022a).
Main contributions. Our contributions are highlighted as follows:
We devise simple algorithm named FedLinUCE that achieves near-optimal regret, low communica- tion complexity and low switching cost simultancously for asynchronous federated contextual linear bandits. In detail, we prove that our algorithms achieves a near-optimal ((dVT) regret with merely (dMM) total communication complexity and ((dM²) total switching cost. Here M is the number of agents, is the dimension of the context and T Em T'm the total number of rounds with M
Tm being the number of rounds that agent m participates in. When degenerated to single-agent bandits, the regret of our algorithm matches the optimal regret Ö(dVT) (Abbasi- et al. 1).
We also prove an Q(M/ log(T/M)) lower bound for the communication complexity. Together with the (dd22 upper bound of our algorithm, suggests that there is only an ((dM) gap between the upper and lower bounds of the communication complexity.

---

We identify the issue of ill-defined filtration caused by the unfixed order of interactions between agents and the environment, which is absent in previous synchronous or single-agent settings. We tackle this unique challenge by connecting the local concentration of each local agent's s data and the global concentration of the aggregated data from all agents. We believe this proof technique of independent interest for the analysis of other asynchronous bandit problems.
Notation, For any positive integer n, we denote the set (1,2,....,n) by [n]]- We use I to denote the d x d identity matrix. We use O to hide universal constants and O to further hide poly-logarihhmic terms. For any vector R& and positive semi-definite Σ E pddd we denote ||>||>> vx Ex.
2 Related Work
We review related work distributeedffederated bandit algorithms stratified by the type of bandits: (1) multi-armed bandits, (2) stochastic linear bandits and (3) contextual linear bandits.
Distributed//federated multi-armed bandits. There is a vast literature distributed/federated multi-armed bandits (MABs) (Luu and Zhao, 2010; Szorenyi et al., 2013; Land gren et al., 2016 Chakraborty et al., 2017: Landgren et al.) 2018;; Martinez-Rin Rubio et al. 2019 Sankararaman et al.
et al. 2019 2019020000 Zhu et al. (021). to mention a few. However, none of these algorithms
can be directly applied to linear bandits, needless to say contextual linear bandits with infinite decision sets.
Distributeed/eddrrate stochastic linear bandits. In distributed/federrted stochastic linear bandits. the decision set is fixed across all the rounds E [7'] and all the agents m E [M.] Wang et al. (019 proposed the DELD algorithm for distributed stochastic linear bandits on both star-shaped network and P2P network. Huang et al. (202T) proposed an arm elimination- -baeed algorithm called Fed-PE for federated stochastic linear bandits on the star-shaped network. Both algorithms are in the synchronous setting and require full participation of the agents upon the server's 's request.
Distributeddfeddrraee contextual linear bandits. The contextual linear bandit is more general and challenging than stochastic linear bandits, because the decision sets can vary for each f and m. In this setting. Korda et al. (2016) considered P2P network and proposed the DCB algorithm based on the OFUL algorithm in Abbasi-
Yadkori Yadkoi- al. (201T). Wang et al. (2019) considered both star-shaped
and P2P communication networks and achieved the near-optimal (dv regret in the synchronous setting Dubey and Pentland (2020) further introduced the differential privacy guarantee into the setting of Wang et al. (2019). Li and Wang (2022b) extended distributed contextual linear bandits to generalized linear bandits (Filippi et al.] 2010 Jun al. (017) in the synchronous setting. Li and Wang (202a)) proposed the first asynchronous algorithm for federated contextual linear bandits with the star-shaped graph and achieved a near-optimal ((vTT) regret. However, their setting is different from ours in two aspects: (I) the upload triggered by an agent will lead the server to trigger download possibly for all the agents in their setting. In contrast, the upload triggered by an agent will only lead to download to the same agent in our setting; (2) their regret guarantee relies on a stringent regularity assumption on the contexts, which basically requires the contexts to be stochastic. As comparison, the contexts in our setting can be even adversarial, which exactly the standard setting of contextual linear bandits (Abbasi-Yadkori et al., 2011 Li et al. 2019). This difference in the setting makes our algorithm a truly asynchronous contextual linear bandit algorithm but also makes our regret analysis more challenging.
For better comparison, we compare our work with the most related contextual linear bandit algorithms in [able
3 Preliminaries
Federated contextual linear bandits. We consider the federated contextual linear bandits follows: At each round & E [T'] an arbitrary agent m, E [M] is active for participation. This agent receives a decision set D, C 2d picks an action x; E D,,, and receives a random reward rg. We assume that
IIn the original paper of Wang 2019), the regret bound expressed as Õld MT). The T in their paper equivalent to the T'm in ours, their d' 'T dVMT
should be understood d under notation.
3

---

Setting
Algorithm
Regret
Communication
Low sww-swiiching
No euta asarpp ornieon
Albow froe paticipttin
OFUL
Single-agent
d./Tlog'T
N/A
/
x
Abbusi-Yidkari
Federated
DisLinUCE
dvTlog2
dM
x
x
(Sync.)
Wang at
Federated
Async-LinUs
dv dvTlogT
dM² log
X
(Asyne.)
Li and Wang 20226
Federated
FedLinUCE
do
dM² log
(Asyne.)
(Our Algorithm
Table Comparison our result with baseline approaches for contextual linear bandits. Our result achieves near-optimal regret under low communication complexity. Here d is the dimension of the context, M is the number of agents, and T = >m= Tm with each T,, being the number of rounds that agent m participates in.
the reward ry satisfies r; = (xe, 0*) + 1/t all E [T]. where 7/t is conditionally independent of X given X1:t-1, M1.:t T1:t-1- More specifically, make the following assumption 7/., 0 and D which is a standard assumption in the contextual linear bandit literature (Abbasi- Yadkori et al. 2011 Wang et al. 2019 Dubey and Pentland 2020).
Assumption 3.1. The noise Y). is R-sub-Gaussiin conditioning on X1Is, mia and Tia-1, i.e.
E [[ X1:t; M1:1, r1:-1] - exp(RRX2/2) for any À E R.
We also assume that ||0|12 < S and ||x|| S L for all action E Di, for all E [T].
Notably, we assume my can be arbitrary for all t, which basically says that each agent can decide whether and when to participate not Our setting is more general than the synchronous setting in Wang et (2019); Dubey and Pentland (2020), which requires a round-robin participation of all agents.
Learning objective. The goal of the agents is collaboratively minimize the cumulative regret defined as
Regret (T)= Σ
max 0*) (xx, 07) xED,
Σ
x Xx, 0")
(3.1)
To achieve such a goal, we allow the agents to collaborate via communication through the central server. Below we will explain the details of the communication model.
Communication model. We consider star-shaped communication network (Wang et al. 2019 Dubey and Pentland 2020) consisting of central server and M agents, where each agent can communicate with the server by uploading and downloading data. However, any pair of agents cannot directly communicate with each other. We define the communication complexity as the total number of communication rounds between agents and the server (counting both the uploads and downloads) (Wang et al. 2019 Dubey and Pentland 2020 Li and Wang 2022a). For simplicity, we assume that there no latency the communication channel.
consider the asynchronous setting, where the communication protocol satisfies: (1) each agent decide whether not participate in each round. Full participation is not required, which allows temporarily offline agents; and (2) the communication between each agent and the server is asynchronous and independent of other agents without mandatory download required by the server.
Switching cost. The notion of switching cost in online learning and bandits refers to the number of times the agent switches its policy (i.e., decision rule) (Kalai and Vempala 2005 Abbasi- Yadkori al. 2011: Dekel et al., 2014; Ruan et al.) (02T). In the context of linear bandits, corresponds to the number of times the agent updates its policy of selecting
action from the decision set (Abbasi-Yadkori et al.) 201T). Algorithms with low switching cost are preferred in practice since each policy switching might cause additional computational overhead.
'Without loss of generality, we can assume that it cannot happen that more than one agent participate at the time. Therefore, there is always valid order of participation indexed [7']

---

Algorithm I Federated linear UCB (edCi)UUB)
1: Initialize m, _1 XI, mm,1 1 0, b 0 and D, 0 for all E [M]
2: for round f = = ,.,...., do
3: Agent my is active
4: Receive D; from the environment
5: Select X + argmaXxED, (mm,,, x) + B /||x||> med
/* Optimistic decision */
6: Receive r1 from environment
7: Im t Ele m + X,X,", bloc
Dm2 f- bloe m,.r-1 + T;X;
/* Local update */
8:
if det((Em (Emii +loe m.,t) >> (1 + a:) (E then
9: Agent my sends mm, and bi server
/+ Upload */
Le + Le + Eloe
bye < -b + bloc mant
/* Global update */
11:
loc + O, ble +0
mi.
12:
Server sends Ejer and byet back to agent my
/* Download */
13:
Emi,++1 <- Sser bm,,+4 < bed
14:
P m + E Σ-1 m 11 bma,t+
Compute estimate */
15:
else
Em < Em,t.
bm bm,ts
0mg O Omnet
17:
end if
for other inactive agent m E [M] {me) do
19: Em,t+1 t Em,,, b & bn,t, 0m,e+1 +- 0m,t
20:
end for
21:
end for
The Proposed Algorithm
propose a simple algorithm based on the principle of optimism that enables collaboration among agents through asynchronous communications with the central server. The main algorithm is displayed in A Algorithm| T
For clarity, we first summarize the related notations in Table 2
Specifically, in each round t E [7], agent m, participates and interacts with the environ- ment (Line B). The environment specifies the decision Dj (Line 4. and the agent m, se- lects the action based on its current optimisitic estimate the reward (Line 5 Here the bonus term B |||||| >mh reflects the uncertainty of the
Notation
Mcaning
0 m
estimate of l* data used compute Pn,t local data for agent m
E,,,, Dynt b
mnt m.t Sver bar m.
data stored at the server
estimated reward (0m,,e x) and encourages ex- ploration. After receiving the true reward Te from the environment, agent m, then updates its local data (Line
Table 2: Notations used in Algorithm
The key component of the algorithm is the matrix determinant-basee criterion (Line S which evaluates the information accumulated in current local data. If the criterion is satisfied, it suggests that the local data would help significantly reduce the uncertainty estimating the model 0". Therefore, agent m, will share its progress by uploading the local data to the server (Line 9 so that it can benefit other agents. Then the server updates the global data accordingly (Line 10 Afterwards, agent m, downloads the latest global data from the server (Line 12) and updates its local data and model (Line 13 14). If the criterion in Line g is not met, then the communication between the agent and the server will not be triggered, and the local data remains local and unshared for agent my (Line 16.. Finally, all the other inactive agents remain unchanged (Line
Note that in Algorithm I the communication between the agent and the server (Line and 12 involves only the active agent in that round, which is completely independent of other agents. This is in sharp contrast to existing algorithms. For example, in the main algorithm in [i and Wang (022a upload by any agent may trigger other agents to download the latest data, while our algorithm does not mandate this. On the other hand, many existing algorithms for multi-agent settings (c.g., Wang

---

et al. (0199) require all agents to interact with the environment in each round, which essentially require full participation of all the agents.
The determinant- criterion in Line / has been a long-standing design trick in contextual linear bandits that help address the issue of unknown time horizon and reduce the switching cost ".bbasi-Yadkon et al. 201T Ruan et al. 202T). For multi-agent bandits, such criterion has also been used to control the communications complexity (Wang et al.] 2019 Dubey and Pentland 2020
Li and Wang 2022a This is because the need for policy switching or communication essentially ly reflects the same fact: enough information has been collected and it is time to update the (local) model. Indeed, achieving low communication complexity and low switching cost are unified in our FedlinUCB algorithm in the sense that the communication complexity is exactly twice the switching cost. Furthermore, using lazy update makes our algorithm amenable for analysis, which will be clear
later Section 6 In addition, we leave a > a tuning parameter as controls the trade-off between the regret and the communication complexity.
5 Theoretical Results
We now present our main result on the theoretical guarantee of Algorithm !
Theorem 5.1. Under Assumption 3.1 for Algorithm if we set the confidence radius , = vAS +
(VI+ Ma Mv2a) RR/ dlog (11 TL2 (minn(a, ())))/ /6) + vāS). then with probability at
least 1- 8, the regret in the first T rounds can be upper bounded by
Regret(T) x 2dSLM log(1 + /1) + 2/2(11 + Ma)3 log(1 + TT,//A)
Moreover, the communication complexity and switching cost are both bounded by log 2 d(M- 1/a) log(1 + TL2 TTT/(Ad))) (Add).
Remark 5.2. Theorem 5.1 suggests that if we set the parameters a = 1/M² and A = 1/S²
in Algorithm [ then its regret is bounded by ((Rv/T) and the corresponding communication complexity and switching cost are both bounded by (ddM²) This choice of parameters yields the regret bound and the communication complexity presented in Table
As a complement, we also provide a lower bound for the communication complexity as stated the following theorem. See Appendix D for the proof.
Theorem 5.3. For any algorithm Alg with expected communication complexity less than OMM OM//log(TT (TM)) there exist a linear bandit instance with R = L S such that for T 2 Md, the expected regret for algorithm Alg is at least ((dv
Remark 5.4. Suppose each agent runs the OFUL algorithm (Abbasi- Yadkori et al. 2011) separately, then each agent m E [M] admits an (d)TTm) regret, where Tn, is the number of rounds that agent m participates in. Thus the total regret of M agents is upper bounded by ΣM Ö(VTm) =
Ö(d MT). Theorem 5.3 implies that for any algorithm Alg, if its communication complexity is less than (M/ log /M )). then its regret cannot be better than naively running M independent OFUL algorithms. In other words, Theorem 3. suggegss that in order to improve the performance through collaboration, an () communication complexity is necessary.
6 Overview of the Proof
When analyzing the performance of FedLinUCB, we face a unique challenge caused by the asyn- chronous communication. as illustrated in Figure [ Here (Xm,t. Tm..)) denotes the decision and the noise for agent m in its own t-th round. Specifically, in the synchronous setting, the filtration is generated by all the data collected by all agents, i.e., F. o (xm,ee Mm,, tmm. the green dashed rectangle. This kind of filtration is well-defined since all agents share their data with each other at the end of each round. In sharp contrast, in our asynchronous setting, the data at the server can be generated by an irregular set of data from the agents, as marked by the blue rectangles. Such data pattern can be arbitrary and depends on the data collected in all previous rounds, which prevents us from defining fixed filtration as we can do in the synchronous setting, Since the
as marked by

---

application of standard martingale concentration inequalities relies on the well-defined filtration, they cannot be directly applied to our asynchronous setting.
To circumvent the above issue, we need to ana- lyze the concentration property of the local data for each agent and then relate it to the concentra- tion of the global data, so that we can control the sum of the bonuses and hence the regret. This requires a careful quantitative comparison the local and global data covariance matrices, which is enabled by our design of determinant- criterion. The details will be further explained in Section 6.2 the next subsection, we present the key ingredients of the proof of Theorem 5.1
Agent
Agent 4
Agent
Nin M
(oga 22.22
Kax %
[gg 9s.1)
R2
(Kga Read
2
R3
(gga Raa
Ka
Os
84
(Kage Rize
Na Roye)
[Kgp %4a
(Iiz Via)
(1.)
(Kggs Res
(Raya
(Kg Bas
Figure 1: Illustration of ill-defined filtration.
Remark 6.1. Recall the notations in Table 2 where the values of those matrices and vectors might change within each round. To eliminate the possible confusion, from now we follow the convention that all matrices and vectors the analysis correspond to their values at the end of each round in Algorithm
6.1 Analysis for communication complexity and switching cost
We first analyze the communication complexity and switching cost of Algorithm For each 2 0, we define
T =t E [T] det 2 Ad)
(6.1)
We divide the set of all rounds into epochs (Ti, + I,..., T++1 }} for each i > 0. Then the communication complexity within each epoch can be bounded using the following lemma.
Lemma 6.2. Under the setting of Theorem 5.1 for each epoch from round :; to round T++1 1, the number of communications in this epoch is upper bounded by 2(M + 1/a).
Proof of Theorem 5.7 communication complexity and switching cost. It suffices to bound the num- ber of epochs. By Assumption 3.1 we have ||xe||2 2 S for E [T]. Since Dnp is positive definite, by the inequality of arithmetic and geometric means, we have
tr E
x ))
det Σ
tr
AI +
1=1
T
TI22
d
|
la
1+
Ad
Then recalling the definition of epochs based
6.1
we have
det
1 TT22
max 2 0 T; # logz
2T
S log d dlog
d
Xd
Therefore, the total number of epochs is bounded by log d (1 + TL? (TL2)(Ad)). Now applying Lemma 6.2 the total communication complexity is bounded by 2log d(M + 1/a) log(1 (Ad)() Note that in Algorithm each agent only switch its policy after communicating with the server, so the switching cost is exactly equal to half of the communication complexity. This finishes the proof for the claim on communication complexity and switching cost in Theorem 5.1
6.2 Analysis for regret upper bound
The regret analysis for Theorem 5.1 is much more involved, and it relies on a series of intermediate lemmas establishing the concentration.
Total information. We define the following auxiliary matrices and vectors that contain all the information up to round L:
MI"l = XI Σ
x.X,
bill
rx
u
m:x:
(6.2)
im
7

---

where 7/ == r; (x, )*) is R-sub-Gaussian Gaussian noise by Assumption 3.1 In our setting, D; b;" u, are not accessible by the agents due to asynchronous communication, and we only use them to facilitate the analysis. With this notation, we can further define the following omnipotent estimate:
0 (Σ.)) bb
(6.3)
As direct application of the self- normalieed martingale concentration inequality (Abbasi- Yadkori et al. 2011), we have the following global confidence bound due to the concentration of Σ and b;"..
Lemma 6.3 (Global confidence bound; Theorem 2, Abbasi-Yadkori al. 2011). With probability
least 1 6, for each round t [T], the estimate 0all in 6.3 satisfies
|0
لxاااا I /d ((1 + TL2/A)/)) VAS.
Per-agent information. Next, for each agent m E [M], we denote the rounds when agent m communicate with the server (i.e., upload and download data) as {fm, m.. J. For simplicity, ar the end of round t, we denote by Nm, (t) the last round when agent communicated with the server (so if agent communicated with the server in round f, then Nt) = t). With this notation, for each round and agent m [M], the data that has been uploaded by agent is them
Nm (t) Σ
Nm (1)
UP m,t
X
up u mi
j=m 1,my m
J 1,my m
Correspondingly, the local data that has not been uploaded to the server is
>
loc m,t
Σ
XjXj
loc m
XyTl. N 1,)+)
1,n= =m
Again, applying the self-normalized martingale concentration (Abbasi- Yadkori et al. 2011 together with union bound, we can get the per-agent local concentration.
Lemma 6.4 (Local concentration). Under the setting of Theorem 5.1 with probability least 1 5, for each round E [T] and each agent m E [M]. holds that
|| (asI+ loc m.)+1)
S Ry dlog (1+TT3/(aN))))) + VAS.
m.t
AA Dle
Moreover, based on our determinant-bast communication criterion, we have the following lemma deseribing the quantitative relationship among the local data, uploaded data and global data.
Lemma 6.5 (Covariance comparison). Under the setting of Theorem 5.1 it holds that
M
AI
Σ Y72 =1
up mi
1
Saae m,t
(6.4)
for each agent E [M]. Moreover, for any 1 S t < < T. if agent m is the only active agent from round & to 12 - 1 and agent m only communicates with the server at round f1, then for all 11+1tt < t2, further holds that
1
Em = + Ma
ΣN!
(6.5)
Combining the above results, we obtain the local confidence bound, which then leads the per-round regret in each round, as summarized in the following lemma.
Lemma 6.6 (Local confidence bound and per-round regret). Under the setting of Theorem 5.1 with
probability at least 1-8, for each t e [T], the estimate 0 satisfies that ||0 im, 1l S 3 for all m E [M]. Consequently, for each round t E [2], the regret round satisfies
A, max (0" x) (0) , x,) S 26 ,
x
'Strictly speaking, the uploaded data only consists of >0 and b m. and here we introduce - and loc solely for the purpose of analysis.

---

Now, we are ready to prove the regret bound in Theorem 5.1
Proof of Theorem 5.7 regret. First, according to Lemma decomposed and upper bounded by
6.6 the regret first round can be
T - xI) S 23 Xx x=llx=n...
T
Regret
Σ
_ and we focus on the agent-action sequence {(m,, x,)) Notice that if an agent m communicate with the server at time & and 12, then the order of actions between round Y and l2 will not effect the covariance matrix for agent In addition, since agent yn does not upload new data between round i and (2, the order of actions from agent m will also not affect other agents' covariance matrix. Thus, without effect the covariance matrix and the corresponding upper confidence bonus, reorder the sequence of active agents such that each agent communicates with the server and stays active until the next agent kicks in to communicate with the server. Such reordering is valid according to the communication protocol as each agent has only local updates between communications with the server.
Now, we only need to control the summation of the upper confidence bonus term 2 [
always
More specifically, we assume that the sequence of round that the active agent communicates with server is 0 = to < t < l2 < ... < IN = T + 1 and from round &; + 1 to f441 - there is only one agent active, that is, Mi, = m1 =
m Then we apply Lemma 6.5 and get that the bonus term for each round 1; < < li+1 can be controlled by
2B x (-m S 2/ Ma X, ||
(6.6)
In addition, to control the bonus term for rounds (4:) we define T, = min E [7) (et( Z ed. For each time interval from T. to T.+1, if an agent m communicate with the server more than once, e.g., agent m communicates with the server at round T² and T; such that T, T2 < T22
T;-1, then for the latter round T22,, the bonus term can be controlled by
2/ XT ( (Em.z,,))- S 23 Ma XT.
2.3 Mo)
XT.
< 223/2(1 + Ma) (
(6.7)
where the first inequality holds due Lemma 6.5 and agent m communicate with the server at the previous round T,,,, the second inequality holds due to Lemma E.4 with the fact that 2, and the last inequality holds due to the fact that Σ T-1 = b On the other hand, for each time interval from T; to T:+1, the bonus term for the first communication can always be trivially bounded by for all agent m. Therefore, the summation of the regret over first communication can be upper bounded by 1. In addition, since the norm each action |x|||2 I L and it implics that we have
det Mله T
(eet < 222'X
del ) S (A+
(6.8)
which implies that the number of different intervals is at most dolog(1 + TL).X). Combining the upper bound of regret in (6.6). 6.7) and 6.8 we have
Regret(T) < dM log(1 + TL2 +
Σ + X 8 1=1
< (elog(1+T13+1 2 + Ma)8 log(1 + TL2/A),
where the last inequality follows from a standard elliptic potential argument (Abbasi- Yadkon et al. 2011). This completes the proof.
Thhre is comminucation happening at to tv. but we include them for notational convenience.

---

7 Experiments
In this section, report numerical simulation results the comparison between algorithm with other baselines. Specifically, we construct a contextual linear bandit instance with feature dimension d 25. In each round the active agent my is uniformly sampled from all M agents. We set the total number of rounds 7 = 30, 000 and test for M = 15 and 30. We compare our FedLinUCB with Async-LinUCB (Li and Wang 2022a and OFUL YbuLLAbbbs--aakko
Yadkori et al. (01T) with
full communication (i.e., the active agent communicates with the server in each round). Due to space limit, further details and more simulation results are deferred to Appendix The code and data for our experiments can be found on Github 5
120
Cumulaative regret
150-
125
Cumulativv
50
75
OFUL, (fuil communication)
50-
OFUL (full communication
20
Async-LinUCB
Async-LinUC8
FedlinUCB
FedlinUCB
5000
10000
1500z
20000
25000
30000
5000
1000C
15000
200c0
25000
30000
M 15. Cumulative regret Round
(h) M 30. Cumulative regret versus Round
Figure 2: Plots of cumulative regret versus round for M 15 (Fig. and M 30 (Fig. 2
comparing FedLinUCB (ours) with Async-LinUCB (Li and Wang 2022a) and OFUL (Abbasi- Yadkori al. 2011) with full communication. The results averaged over 20 runs with the error bars chosen as the empirical one standard deviation.
It is clear from Figure that FedLinUCB outperforms Async-LinUCB (Li and Wang 2022al in terms of regret. Although OFUL with full communication has the smallest regret, its communication cost (2MT) is much higher than ours. Furthermore, we plot the log-scaled regret in Figure 3(c)aan and M(d Appendix B which show that the average regret of our algorithm actually has a rate very close to the optimal rate of OFUL. Overall, the numerical simulation corroborates our theoretical results.
8 Conclusion and Future Work
In this work, study federated contextual linear bandit problem with fully asynchronous com- munication. We propose simple and provably efficient algorithm named FedLinUCB. We prove that FedLinUCB obtains near-optimal regret of order ((dVT) with (ddM²) communication complexity. We also prove a lower bound on the communication complexity, which suggests that an ((M) communication complexity is necessary for achieving near-optimal regret. There still exists an (ddM) gap between the upper and lower bounds for the communication complexity and leave it as future work to close this gap. Another important direction for future work is to study federated linear bandits with decentralized communication network without a central server (i.e., P2P networks). In addition, there potential privacy concerns when the agents upload and download data from the server, and it remains an open problem to devise provably efficient algorithm for asynchronous federated linear bandits with privacy guarantees.
Acknowledgment and Disclosure of Funding
We thank the anonymous reviewers and area chair for their helpful comments. JH and QG are partially supported by the National Science Foundation CAREER Award 1906169 and the Sloan Research Fellowship. The views and conclusions contained in this paper are those of the authors and should not be interpreted representing any funding agencies.
http://gtthub.cmm/ccaa////dddddd
10

---

References
LBBASI-YADKORK Y., PÁL. D. and SZEPESVÁRI, C. (2011). Improved algorithms for linear stochastic bandits. Advances in neural information processing systems 24 2312-2320.
ABE, N., BIERMANN, A. W. and LONG, P. M. (2003). Reinforcement learning with immediate rewards and linear hypotheses. Algorithmica 37 263-293.
AGRAWAL, S. and GOYAL, N. (2013). Thompson sampling for contextual bandits with linear payoffs. In International conference on machine learning. PMLR.
AUER, P. (2002). Using confidence bounds for exploitation-exploraiio trade-offs. Journal of Machine Learning Research 397-422.
CESA-BIANCHI, N., GENTILE, C. and ZAPPELLA, G. (2013). A gang of bandits. Advances in neural information processing systems 26.
CHAKRABORTY, M., CHUA, K. Y. P., DAS, S. and JUBA, B. (2017). Coordinated versus decentral- ized exploration in multi-agent multi-armed bandits. In IJCAI.
CHU, W., LI, L., REYZIN, L. and SCHAPIRE, R. (2011). Contextual bandits with linear payoff functions. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics. JMLR Workshop and Conference Proceedings.
DANI, V., 9, HAYES, T. and KAKADE, S. M. (2008). Stochastic linear optimization under bandit feedback. 2 Annual Conference Learning Theory 355-366.
DEKEL, O., DING, J., KOREN, T. and PERES, Y. (2014). Bandits with switching costs: T 2/3 regret. In Proceedings of the forty-sixth anmual ACM symposium on Theory of computing.
DUBEY, A. and PENTLAND, A. (2020). iiterrentially-prvvatt federated linear bandits. Advances in Neural Information Processing Systems 33 6003-6014.
DURAND, ACHILLEOS, C., IACOVIDES, D., STRATI, K., MITSIS, G. D. and PINEAU, (2018). Contextual bandits for adapting treatment in mouse model of de novo carcinogenesis, In Machine learning for healthcare conference. PMLR.
FILIPPI, S., CAPPE, O., GARIVIER, and SZEPESVÁRI, C. (2010). Parametric bandits: The generalized linear case. Advances in Neural Information Processing Systems 23.
GENTILE, C., LI, S. and ZAPPELLA, G. (2014). Online clustering of bandits. In International Conference on Machine Learning. PMLR.
HUANG, R., WU, W., YANG, J. and SHEN, C. (2021). Federated linear contextual bandits. Advances in Neural Information Processing Systems 34.
JAGADEESAN. M.. WEL, A., WANG, Y.. JORDAN, M. and STEINHARDT, J. (2021). Learning equilibria in matching markets from bandit feedback. Advances in Neural Information Processing Systems 34.
JUN, K.-S., BHARGAVA, A., NOWAK, R. and WILLETT, (2017). Scalable generalized linear bandits: Online computation and hashing. Advances in Neural Information Processing Systems 30.
KALAI, A. and VEMPALA, S. (2005). Efficient algorithms for online decision problems. Journal of Computer and System Sciences 71 291-307.
KARIMIREDDY, S. P., JAGGI, M., KALE, S., MOHRI, M., REDDI, S. J., STICH, S. U. and SURESH, A. T. (2020). Mime: Mimicking centralized stochastic algorithms in federated learning. arXiv preprint arXiv:2008.03606
KORDA, N., SZORENYI, B. and LI, S. (2016). Distributed clustering of linear bandits in peer to peer networks. In International conference on machine learning. PMLR.
LANDGREN, P., SRIVASTAVA, and LEONARD, N. E. (2016). On distributed cooperative decision- making in multiarmed bandits. In 2016 European Control Conference (ECC). IEEE.

---

LANDGREN, P., SRIVASTAVA, V. and LEONARD, N. E. (2018). Social imitation in cooperative multiarmed bandits: Partition-based algorithms with strictly local information. In 2018 IEEE Conference Decision and Control (CDC). IEEE.
LATTIMORE, T. and SZEPESVÁRI, C. (2020). Bandil algorithms. Cambridge University Press.
LI. C. and WANG, H. (2022a). Asynchronous upper confidence bound algorithms for federated linear bandits. In International Conference Artificial Intelligence and Statistics. PMLR.
LI, C. and WANG, H. (2022b). Communication efficient federated learning for generalized linear bandits, arXiv preprint arXiv:2202.01087.
LI, C., WU, Q. and WANG, H. (2021). Unifying clustered and non-stationary bandits. In Interna- tional Conference on Artificial Intelligence and Statistics. PMLR.
LI, L., CHU, W., LANGFORD, and SCHAPIRE, R. E. (2010a). contextual-band bandit approach to personalized news article recommendation. In Proceedings of the 19th international conference on World wide web.
LI, S., KARATZOGLOU, A. and GENTILE, C. (2016). Collaborative filtering bandits. In Proceedings of the 39th International ACM SIGIR conference on Research and Development in Information Retrieval.
LI, T., SONG, L. and FRAGOULI, C. (2020). Federated recommendation system via differential privacy. In 2020 IEEE International Symposium on Information Theory (ISIT). IEEE.
LI, W. WANG, X., ZHANG, R., CUL, Y., MAO, J. and JIN, R. (2010b). Exploitation and exploration in a performance based contextual advertising system. In Proceedings of the 16th ACM SIGKDD international conference Knowledge discovery and data mining.
LI, Y., WANG, C.-H., CHENG, G. and SUN, W. (2022). Rate-optimal contextual online matching bandit. arXiv preprint arXiv:2205.03669.
LI Y., WANG, Y. and ZHOU, Y. (2019). Nearly dinimaxx-ppimal regret for linearly parameterized bandits. In Conference on Learning Theory. PMLR.
LIU, K. and ZhAO, Q. (2010). Distributed learning in multi-armed bandit with multiple players. IEEE transactions on signal processing 58 5667-5681.
MARTÍNEZ-RUne RUBIO, D., KANADE, V. and REBESCHINI, P. (2019). Decentralized cooperative stochastic bandits. Advances in Neural Information Processing Systems 32.
McMAHAN, B., MOORF, E., RAMAGE, D., HAMPSON, S. and Y ARCAS, B. A. (2017). Communication-efficin learning of deep networks from decentralized data. In Artificial in- telligence and statistics. PMLR.
RUAN, Y., YANG, J. and ZHOU, Y. (2021). Linear bandits with limited adaptivity and learning distributional optimal design. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing.
RUSMEVICHIENTONG, P. and TSITSIKLIS, J. N. (2010). Linearly parameterized bandits. Mathemat- ics of Operations Research 35 395-411.
SANKARARAMAN, A., GANESH, A. and SHAKKOTTAI, S. (2019). Social learning in multi agent multi armed bandits. Proceedings of the ACM Measurement and Analysis of Computing Systems 1-35.
SZORENYL, B., BUSA--UUEEEE R., HEGEDUS, I., ORMÁNDI, R., JELASITY, M. and KÉGL, B. (2013). Gossip-based distributed stochastic bandit algorithms. International Conference on Machine Learning. PMLR.
TIE, I.., CAL, K.-Y. and LIN, Y. (2011). Rearrangement inequalities for hermitian matrices. Linear algebra and its applications 434 443-456.
12

---

WANG, P.-A., PROUTIERE, A., ARIU, K., JEDRA, Y. and RUsSo, A. (2020). Optimal algorithms for multiplayer multi-armed bandits. In International Conference on Artificial Intelligence and Statistics. PMLR.
WANG, Y., HU, J., CHEN, X. and WANG, L. (2019). Distributed bandit learning: Near-optimal regret with efficient communication. arXiv preprint arXiv:1904.066 06309.
WANG, Y.-G. (1991). Sequential allocation in clinical trials. Communications in Ceatistics-Theor and Methods 20 791-805.
WU, Q., WANG, H., Gu, Q. and WANG, H. (2016). Contextual bandits in a collaborative en- vironment. In Proceedings of the 39th International ACM SIGIR conference on Research and Development in Information Retrieval.
ZIIU, Z., Zn1, J., LIU, J. and LIU, Y. (2021). Federated bandit: A gossiping approach. In Abstract Proceedings of the 2021 ACM SICMETRICS/nntematiood Conference on Measurement and Modeling of Computer Systems.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A] This work
seeking to develop a mathematical understanding of federated linear bandits.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they chosen)? [Yes]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you are using existing assets (e.g.. code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] We use existing theorems and cite them properly.
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you'l 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsoureing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
13

---

(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "sVXfMNai5-b", "reviewer": "Reviewer_S7tZ", "summary": "The manuscript proposes a federated contextual linear bandit algorithm in the asynchronous setting, where all agents work independently and the communication between one agent and the server will not trigger other agents’ communication. The proposed algorithm obtains a near-optimal regret and low communication complexity. ", "questions": "(a) The proposed algorithm shows that at each time $t$, only one client exchanges parameters to the server. Is this setting reasonable? Does this make the collaboration less effective? Are there any practical applications fit for this setting?\n\n(b) How about the performance of the proposed algorithm in dealing with some real-world applications?\n", "limitations": "(a) In Algorithm 1, the parameters exchanged between the server and the client are $\\Sigma$ and $u$, which may lead to the privacy leakage of local data. I suggest the authors refer to the work [Dubey and Pentland, 2020] to address this issue. \n\n(b) It would be better to conduct some numerical experiments to support the merits of the proposed algorithm. ", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n\n(a) This is the first asynchronous federated linear contextual bandit model considering the following features: (i) Each agent can decide whether or not to participate in each round; (ii) The communication between each agent and the server is asynchronous and totally independent of other agents. \n\n(b) Considering that the order of the interaction between the agent and the environment is not fixed, standard martingale-based concentration inequality cannot be directly applied. This work applies a novel proof technique to solve this issue, which could be interesting.  \n\n(c) The proposed algorithm achieves a near-optimal regret, low communication complexity and switching cost simultaneously.\n\nWeaknesses\n\n(a) The proposed algorithm shows that at each time $t$, only one client exchanges parameters to the server. It seems that this setting is not reasonable and could make the collaboration less effective. \n\n(b) In Algorithm 1, the parameters exchanged between the server and the client are $\\Sigma$ and $u$, which may lead to the privacy leakage of local data. \n\n(c) The motivation of this work is not very clear. The authors should pay more attention to this issue. \n\n(d) There lack of numerical experiments to support the theoretical findings.", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Zz9JJ1-iE4i", "reviewer": "Reviewer_eNSj", "summary": "The paper considers asynchronous federated contextual linear bandits problem, where each agent faces a single contextual linear bandits model and the parameters are the same. The learning objective is to minimize the cumulative regret of all agents. By a novel analysis, the paper prove that a simple algorithm called FedLinUCB enjoys regret upper bound $O(d\\sqrt{MT})$, where d is the dimension of parameter space, M is the number of agents, and T is the time horizon. The paper also gives an lower bound of the communication cost scales $\\Omega(dM)$.", "questions": "As mentioned above, IMHO, there may be some benefits if inactive agents are allowed to download new information. Is it possible to close the gap of communication cost upper and lower bound by personalized event-trigger downloading procedure?\n\n\n------------\nThank the author for the explanation. My concerns are addressed and I decide to keep my score.", "limitations": "Yes", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The primary novelty of the paper is to provide an analysis for fully asynchronous federated linear contextual bandits, where each agent can independently decide whether it communicates with the central server. The paper is well-written and sound.\n\nWhile the independency between agents' communication is new, the algorithm also restricts the inactive agents to download new information from the server.\n", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "GMdZswhy5xR", "reviewer": "Reviewer_BhjP", "summary": "This paper proposes the FedLinUCB algorithm for asynchronous federated contextual linear bandits. The authors prove that the algorithm has a tight regret upper bound and low communication complexity.", "questions": "Why don't you provide simulation results? If my guess is right, in numerical simulation, FedLinUCB would have almost the same performance as [Li and Wang 2022], if not a little worse. But FedLinUCB could still have a smaller communication time.", "limitations": "This part of the paper looks good for me. ", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "1. Strengths\n\t1. Propose a better communication protocol that fits the asynchronous setting;\n\t2. Provide a new method to derive LinUCB's upper bound in the asynchronous setting.\n\t3. The author did a very good job in presenting their work. \n2. Weaknesses:\n\t1. My major concern lies in the significance. The strengths above are not major compared to [Li and Wang 2022, AISTATS]. Because FedLinUCB is a (very) minor modification of [Li and Wang 2022] in communication protocol: given the same communication condition (determinant-based criterion), the difference is only in *how* agent and server communicate. (also see the paper's Table 1's last two rows).\n\t2. Secondly, in my opinion, the originality also does not reach the NeurIPS bar. The model is not new. The algorithmic technique is already broadly used (already in the same model as well). Only the analysis technique is novel, though seems minor (since it only works in this specific federated contextual linear bandits' LinUCB algorithm). \n\n------\nAfter rebuttal: I thank the author for the detail comparison [Li and Wang, 2022] and the additional experiments. My concerns are addressed. I raised my score to weak accept. ", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept