Federated Q-Learning: Linear Regret Speedup with Low Communication Cost
Authors: Zhong Zheng
Fengyu Gao
Lingzhou Xue
Jing Yang
Venue: ICLR 2024 poster (2024)
Keywords: Federated Learning
Reinforcement Learning
Q-Learning
Regret
Communication Cost
Primary area: reinforcement learning
TL;DR: This paper proposes two model-free federated reinforcement learning algorithms that achieve linear regret speedup with logarithmic communication cost.

Abstract: In this paper, we consider federated reinforcement learning for tabular episodic Markov Decision Processes (MDP) where, under the coordination of a central server, multiple agents collaboratively explore the environment and learn an optimal policy without sharing their raw data.  While linear speedup in the number of agents has been achieved for some metrics, such as convergence rate and sample complexity, in similar settings, it is unclear whether it is possible to design a *model-free* algorithm to achieve linear *regret* speedup with low communication cost. We propose two federated Q-Learning algorithms termed as FedQ-Hoeffding and FedQ-Bernstein, respectively, and show that the corresponding total regrets achieve a linear speedup compared with their single-agent counterparts, while the communication cost scales logarithmically in the total number of time steps $T$. Those results rely on an event-triggered synchronization mechanism between the agents and the server, a novel step size selection when the server aggregates the local estimates of the state-action values to form the global estimates, and a set of new concentration inequalities to bound the sum of non-martingale differences. This is the first work showing that linear regret speedup and logarithmic communication cost can be achieved by model-free algorithms in federated reinforcement learning.

Published as a conference paper at ICLR 2024
FEDERATED Q-LEARNING: LINEAR REGRET SPEEDUP WITH Low COMMUNICATION COST
Zhong Zheng, Fengyu Gao, Lingzhou Xue & Jing Yang" The Pennsylvania State University (zv25337, fzg5170, 70, 1zxue, yang i edu
ABSTRACT
In this paper, we consider federated reinforcement learning for tabular episodic Markov Decision Processes (MDP) where, under the coordination of a central server, multiple agents collaboratively explore the environment and learn an op- timal policy without sharing their raw data. While linear speedup in the number agents has been achieved for some metrics, such as convergence rate and sam- ple complexity, in similar settings, it is unclear whether it is possible to design a model-free algorithm to achieve linear regret speedup with low communication cost. We propose two federated Q-Learning algorithms termed FedQ- Hoeffding and FedQ-Bernstein respectively. and show that the corresponding total regrets achieve linear speedup compared with their single-agent counterparts when the time horizon is sufficiently large, while the communication cost scales logarithmi- cally in the total number of time steps T. Those results rely on an event-triggered synchronization mechanism between the agents and the server, a novel step size selection when the server aggregates the local estimates of the state-action values form the global estimates, and set of new concentration inequalities to bound the sum of morttaatie differences. This the first work showing that linear regret speedup and logarithmic communication cost be achieved by model- free algorithms in federated reinforcement learning.
INTRODUCTION
Federated Learning (FL) (McMahan et al. 2017) is distributed machine learning framework, where a large number of clients collectively engage in model training and accelerate the learning process, under the coordination of a central server. Notably, this approach keeps raw data confined to local devices and only communicates model updates between the clients and the server, thereby dimin- ishing the potential for data exposure risks and reducing communication costs. As result of these advantages, FL is gaining traction across various domains, including healthcare, telecommunica- tions, retail, and personalized advertising.
On a different note, Reinforcement Learning (RL) (Sutton & Barto 2018) is a subfield of machine learning focused on the intricate domain of sequential decision- Decision Process (MDP), the primary objective of RL is to obtain an optimal policy through sequen- tial interactions with the previously unknown environment. RL has exhibited superhuman perfor-
Often modeled as a Markov
mances in various applications, such games (Silver et al., 2016 2017: 2018 Vinyals al. 2019) robotics (Kober et al. 20133] Gu et al. 2017). and autonomous driving Yurttever et al. 2020). and garnered increasing attentions in different domains.
However, training an RL agent often requires large amounts of data, due to the inherent high di- mensional state and action spaces (Akkaya et al. 2019 Kalashnikov al., 2018), and sequentially generating such training data is very time-consuming (Nair et 2013). thus has inspired a line of research that aims extend the FL principle the RL setting. The FL. framework allows the agents to collaboratively train their decision-making models with limited information exchange between the agents, thereby accelerating the learning process and reducing communication costs. Among them, some model-bar based algorithms (c.g., Chen et al. (2023)) and pasecy-based algorithms (c.g..
"I.. Xue and J. Yang co-corresponding authors.

---

Published as a conference paper at ICLR 2024
Fan et al. (202I) have already exhibited speedup with respect to the number of agents for learning regret or convergence rate.
Also, there is collection of research focusing on model-free federated RL algorithms, which have shown encouraging results. Such algorithms build upon the classical value-based algorithms such as Q-learning (Watkins 1989), which directly learns the optimal policy without estimating the un- derlying model. Among them. Jin et al. (2022) considered a heterogeneous setting where the agents interact with environments with different but known transition dynamics, and the objectíve is to ob- tain a policy that maximizes the overall performance in all environments. It proposes two federated RL algorithms, including Q--earming-basee based algorithm called QAvg, and proves their convergence. Liu & Olshevsky (2023) investigated distributed TD-learnin with linear function approximation and achieves linear convergence speedup under the assumption that the samples are generated in an identical and independently distributed (i.i.d)) fashion. [Khodadadian et al. (2022) proposed feder- ated versions of TDD-lernnig and Q-learning and proved a linear convergence speedup with respect to the number of agents for both algorithms under Markovian sampling. [Wo et al. (2023) stud- ied infinite-horizon tabular Markov decision processes (MDP) and proposed both the synchronous and asynchronous variants of federated Q-learning. Both algorithms exhibit a linear speedup in the sample complexity. We note that under the aforementioned algorithms, the clients do not adap- tively update their exploration policy during the learning process. As result, they do not have any theoretical guarantees on the total regret among the agents
In this work, aim to answer the following question:
Is it possible to design a federated model-free RL algorithm that enjoys both linear regret speedup and low communication cost?
We give an affirmative answer to this question under the tabular episodic MDP setting. Specifically, assume central server and M local agents exist in the system, where each agent interacts with an episodic MDP with S states, A actions, and H steps in each episode independently. The server coordinates the behavior of the agents by designating their exploration policies, while the clients execute the policies, collect trajectories, and form "local updates". The local updates will be sent to the server periodically to form "global updates" and refine the exploration policy. Our contributions can be summarized as follows.
Algorithmic Design. We propose two federated variants of the Q-learnng algorithm (Jin et al., 2018), termed as TedQ-Hoeffding and
respectively. Those two algorithms fea- ture the following elements in their design: 1) Adaptive exploration policy selection. In order to achieve linear regret speedup, it becomes necessary to adaptively select the exploration policy for all clients, which is in stark contrast to the static sampling policy adopted in Khodadadian et al. (002)): Woo et al. (2023). 2) Event-triggered policy switching and communication. On the other hand, reduce the communication cost, it is desirable to keep the exploration policy switching to a minimum extent. This motivates us to adopt an event-triggered policy switching and commu- nication mechanism, where communication and subsequent policy switching only happen when certain condition is satisfied. This naturally partitions the learning process into rounds. 3) Equal weight assignment for global aggregation. When the central server updates the global estimates of the Q-value for given state-action pair (x., a) at step h, we assign equal weights for all new visits to the tuple (xr, a, h) within the current round. As result, local agents do not need to send the collected trajectories to the server. Instead, it only needs to send the empirical average of the estimated values of the next states after visiting (x, a, f)) to the server.
Performance Guarantees. Thanks to the careful design of the policy switching. communica- tion, and global aggregation mechanisms, linear regret speedup in the number of agents compared with their single-agent counterparts (Jin) ct al. 2018 Bai et al. 2019) when the total number of steps T' is sufficiently large, while the communication cost scales in ( 2 A log(T/M)) To the best of our knowledge, those are the first model-free federated RL algorithms that achieve linear regret speedup with logarithmic communication cost. We compare the regret and communication costs under multi-agen agent tabular episodic MDPs in Table
and RedQ-Bernstein provably achieve
A comprehensive literature review is provided in Appendix
2

---

Published as a conference paper at ICLR 2024
Table 1: Comparison of Related Algorithms
Type
Algorithm (Reference)
Regret
Communication cost
Multi-batch RL (Zhng et al. 2022
SMMT)
Model-based
APEVE QQao et al. 2022
Byzan-UCBVI (Chen et al. 2023
O(VH*SAAMT)
O(M
Concurrent Q-UCB2H [Bai et al.
2019
O(VIASAAMT)
O(MIT)
Concurrent Q-UCB2B (Bai ct al
2019
OIVI
O(MT)
Model-free
Concurrent UCB-Advantage Zhang et
2020
O D(HHSSMMT))
O(MT)
WedQ-Hoeffdingg (this work)
O O(MHS
O(M Alog(T/M O 5* (og(T/M))
BesQ--ernsteinn (this work)
OLVHSSAMT)
H: number of steps per episode; T: total numher of steps; S: number of stares; A: number of actions; M: numher of agents. not discussed.
Technical Novelty. While the equal weight assignment during global aggregation is critical to reducing the communication cost in our design, it also leads non-trivial challenge for the corresponding theoretical analysis. This is because the specific weight assigned to each new visit depends on the total number of visits between two model aggregation points, which is not causally known when (Ir a, h) is visited. As result, the weights assigned to all visits of (ær a, h) do not form martingale difference sequence. Such non-martingale property makes the cumula- tive estimation error in the global estimates of the value functions difficult to track. In order to characterize the concentration of the sum of non-martingale differences, we relate the non- martingale difference sequence with another martingale difference sequence within each round. Due to the common factor between those two sequences in each round, we are then able to bound their differencce roundwisely. We believe that the techniques developed for proving concentration inequalities on the sum of non-martingale differences will be useful in future analysis of other model-free federated RL algorithms.
BACKGROUND AND PROBLEM FORMULATION
Notations. Throughout this paper, we assume that 0/0 For any C N, we use [C] denote the set (1, ..... C). We use [(x]] to denote the indicator function, which equals when the event true and equals otherwise.
2.1 PRELIMINARIES
We first introduce the mathematical model and background on Markov decision processes.
Tabular Episodic Markov Decision Process (MDP). A tabular episodic MDP is denoted as M := (S, A, H, P,,,, where S is the set of states with S S, A is the set of actions with |.A| A, H is the number of steps in each episode, := {P, /== } is the transition kernel so that (. x; a) characterizes the distribution over the next state given the state action pair (a,, a) at step h, and
r = { is the collection of reward functions. In this work, we assume I'M (I, a) E [0, 1] is
deterministic function of (Ir a). while the results can be easily extended to the case when rh is random.
In each episode of M, an initial state xı is selected arbitrarily by an adversary. Then, at each step h E [H) an agent observes state E S, picks an action ag E A, receives reward ra r'k (2,,, 0s. and then transits to next state Fh+1- The episode ends when an absorbing state xH+1 reached.
Policy, State Value Functions and Action Value Functions. A policy π is collection of H functions [A 8 AA)
hE(H] where A is the set of probability distributions over A. policy is deterministic if for any E S, (x) concentrates all the probability mass on action E A. In this case, we simply denote (x)
We use VØ S + R to denote the state value function at step h under policy so that VT (z) equals the expected return under policy æ starting from 2b = æ. Mathematically,
H
(x) = Σ
E wnw (Tw, aN) Ir = x].
3

---

Published as a conference paper at ICLR 2024
Accordingly, we also use Q7 : 8 A - IR to denote the action value function at step h, i.e.,
M
(((,,a):-n(8s.000
Σ W=h+1
[Pre (rw,, aw) 1. 2; On a)
Since the state and action spaces and the horizon are all finite, there always exists an optimal policy
T that achieves the optimal value (z) = sup, Ve (x) V/ (x) for all x E S and h E [H] Azzr et al. 2.17 For ease of exposition, Then, the Bellman equation and the Bellman optimality equation can be expressed as:
denote [PA VP (z, a) PP Vi41 (x')-
(z) = Ea-na (2) 107 (2)
(ī) m (z,) (x = (nh + + + (0,a)
(x. 0) (Th, PAV. V V (z) Vx E
A+1 (I,
and
(1)
(=+1(=) 0, V
2.2 THE FEDERATED RL FRAMEWORK
In this work, we consider a federated RL setting with central server and M agents, each interacting with an independent copy of the MDP M in parallel. The agents can communicate with the server periodically. Depending on the specific algorithm design, the agents may send different information (e.g., reward or estimated V-values Vn, to the central server. Upon receiving the local informa- tion, the central server then aggregates and broadcasts certain information to the clients to coordinate their exploration. Note that, just in FL, communication is one of the major bottlenecks, and the algorithm has to be conscious of its usage. In this work, we define the communication cost of an algorithm as the number of scalars (integers real numbers) communicated between the server and clients. We also make the assumption that there is no latency during the communications, and the agents and server fully synchronized (McMahan al. 2017).
Let Fh m. be the policy adopted by agent m at step h in the s-th episode, and x:"h be the corre- sponding initial state. Then, the overall learning regret of the M clients over T = HJ steps be expressed as
J
Regret (T) = Σ
m. -v," with (0 (z)
mE[M] ==1
Here, is the number of episodes and stays the same across different agents due to the synchroniza- tion assumption.
3
ALGORITHM DESIGN
In this section, we elaborate model-free federated RL algorithm termed as The Bernstein-type algorithm, termed as FedQ-Bed Bernstein, will be introduced afterward.
3.1 THE FOEF-ING ALGORITHM
The algorithm proceeds in rounds, indexed by is [K]. Round & consists of n² episodes for each agent, where the specific value of n² will be determined later. Before we proceed, we first introduce the following notations. For the j-th (j E [n*1) episode in the k-th round, we use zmnkkJ to denote m.k.j m.kk. } denote the correspond- the initial state for the m-th agent, and use (x (m.j.. aa .rh
ing trajectory. Denote ni m.,k (xx, a) as the total number of times that the state-action pair (z, a) has m.kk""
been visited at step h during round A by agent m. i.e., ni m. (x,aa) = Σ [[ (urm...s'
,4
(r,, a)}, and let (x, a) = ΣM= mi m.k (Ix a). i.e, the total number of visits for (x, a) at step during round l among all agents. We also denote N/ a) as the total number of visits for (æ, a, h) Eme Σ mn 1= [( a am.k'
among all agents before round k, i.,, (2, (a, a)).
m.
We also use (V. S + RY and (Q) S x A A- RJH to denote the "global" estimates of the state value function and action value function before the beginning of round k. Meanwhile,
4

---

Published as a conference paper at ICLR 2024
mik hh+1 (1, a) to denote the "local" estimate of the expected return starting at step h + agent in round & given (on, an) = (xr, a), and use o (2,a) a) to denote the corresponding global estimate.
We then specify each individual component of the algorithm as follows.
Coordinated Exploration for Agents. At the beginning of round k. the server decides determin- istic policy τÃ {
/f h= and then broadcasts it along with (N (T)) and (x) (z, a) = 0, Q (xx a) = V (x) = (1, ESE [H) and π is an arbitrary deterministic policy.
to all of the agents. When k = 1, (2,
Once receiving such information, the agents will execute policy n& and start collecting trajectories.
Event-Triggered Termination of Exploration. During exploration, every agent will mon- itor n ma.k (zz, a), i.e. the total number of visits for each (zz a, triple within the current round. For any agent m, at the end of each episode, if any (z, o, h) has been visited by max |1|MMHHH M1( (2, a)] times by agent m, the agent will send a signal to the server, which will then request all agents to abort the exploration.
The termination condition guarantees that for any (x, a, h, k) E x A [M] x [K].
m,kk n% (ar, a) S max (1,
N (x,, a)
MH +1]
and for each k E [K], there exists at least one agent m. such that equality is met for a (xr, a, h, m)- tuple. The inequality limits the number of visits in a round and important for introducing our server-side information aggregation design shortly. Meanwhile, the existence of equality guaranteess that a sufficient number of new samples will be generated a round, which is the key to the proof of Theorem 4.2 about the low communication cost.
Local Updating of the Estimated Expected Return. Each agent updates the local estimate of the expected return .m,kk (x. a) at the end of round i as follows: 1//1
m.kk Uh (I, a)
1
Σ 5=1
V
(m.kk I((x) aaathhsaagkk aa.. - aI) wh E [M],
Thp m.k (m. (z,a) a)
i.e., for each (ar, a) visited at step h during round k, 1/+1 is obtained by taking the empirical average of the global estimates of the value of the next visited state in the current round
mn.k
m,. Next, each agent m sends {ra (z, +H (n)))a m.k (r, 7h (=))),,, and { (z, n (2r))2,, to the central server for aggregation.
Server-side Information Aggregation. Denote a = H+1 0g = 1, 00 = 0 for N 1, and H+#
of oi -4--1111 (1 oz), A sish. L. We also denote a (4,12) -I (x) for any positive integers t < t2.
Then, after receiving the information sent by the agents, for each (x,, a, h) tuple visited by the agents, the server sets - N (I. a), th = -v/+1 (I,a) a), Gagg 1 a (t" + 1, th) and 8 (1r a,
2 Ei= f by for some confidence bound b, to be determined later. When there is no ambiguity, we will also use 3 to represent (*, a, h). Then the server updates the global estimate of the value functions according to one of the following two cases.
Case 1: Nº. (z, a) < 2M + 1) =: in- Due to Equation (2) this case implies that each client can visit each (I,,a) pair at step ht most once. Then, we denote < mi m2... < m I M as the agent indices with ny
m. (x, > O. The server then updates the global
estimate of action values as follows:
-4-
Q1+t(2,,) = (l-aagg) Q (z, a) + an
Σ ge 'te (2, + 3*/2. (3)
. Case 2: N (x, a) 2 io. In this case, the central server calculates v (x, a) as
M
- ( a)
mikk h (a, a)n m.k (x, a)
n (x, a) m=1
5

---

Published as a conference paper at ICLR 2024
and updates the Qestimmate
(z,a) (1-g ( (x, Gagg (ra a) + u (z, a)) 12h...
(4)
After finishing updating the estimated Q function, the central server updates the estimated value function and the policy as follows:
H, max Oh+1 max (e.d]]. v(a,h) ES [M]] a'EA
ve+1
(x) (x) min
(5)
AA
J++1 (x) arg max 2%, (x,a'), ((x, ESx a'EAA
(6)
The algorithm then proceeds round k +
Algorithms/ [nnd] 2 formally present Hoeffding-type design. Inputs Ko, To Algorithms | are termination conditions where Ko limits the total number of rounds and To limits the total number of samples generated by all the agents before the last round.
Algorithm FedQ- Hoeffding (Central Server)
1: Input: To. Kg E N..
2: Initialization: 1: = 1, (2, a) 0, (x, = (2(()) = H, a, S Ax [H] and
nejm is arbitrary deterministic policy.
3: while HΣ Mn < To & S Ko do
4: Broadcast ,² {NV (ar, (x)))) and (V)())) to all clients.
5: Wait until receiving an abortion signal and send the signal to all agents.
Receive (rx (x. n 2,,h. (n mi (I,, (xr)))))) and (um.k (2c, m (x))), from clients.
6:
Calculate No+1 (z, a), n (z, a), o (z, ((r,)) ESX [M] with a =x(x).
7:
8:
for (I, a) h) E Ax [ do
9:
i 4 (x) or (1 0 then
10:
oh (r, +- ()
11:
else if N a) < 4 then Update 2++ (z, a) according to Equation 3
12:
13:
else
14:
Update + (x. a) according to Equation
15:
end if
end for
17:
Update p--1 and A+ according to Equation and Equation 6
lo 2+ l: +
19: end while
Algorithm FedQ- (Agent m in round k)
1: m/ ni a) "/ (z, r= a) = 0, V(z, a, h) S x A x [H].
2: Receive , (Nk (ær, (x))),, and (V) from the central server.
3: while no abortion signal from the central server do
4: while n (In, an) < max {I, [1LWMIH N (In, and]] V(z, ES [H] do
5: Collect a new trajectory {(IA, an, Th) H with ag = (In).
6: Th (In, ax) + ni (Ih, an) + 1, o (Th, an) +- oh 1 an) + V (x and
m
Ti(IN,, an) + Th, Vh [H].
7:
end while
8: Send an abortion signal to the central server.
9:
end while
mikk 10: ni m.k (I,a) a) ni (Ir, a), uh (x, (e V(r h) E E [H] with =/(x).
(m.a(
11: Send (ra(æ, (z))) mn
m.k (x (x)))e and (unth (x))) to the central server.

---

Published as a conference paper at ICLR 2024
3.2 INTUITION BEHIND THE ALGORITHM DESIGN
Q-estimate Update in Single-agent Setting. Before we elaborate the intuition behind our algorithm design, we first provide a brief review of the Q-value estimate updating step under the Q-UCB2H algorithm (Bai et al. 2019) in the single-agent setting. Similar to FedQ-Hoofffingg. Q-UCB2H also has round-based design, where the agent updates the value function estimates at the end of each round. With a slight abuse of the notation, we use the same symbols as in Section 3.1 to denote the quantities in the single-agent setting.
In round k for given triple (z, a,. h) such that n" (z. a) > O, we denote the next states for all of 1et
the visits within the round as (=n+1e))= 141. Then, the Q-estimate is updated sequentially and recursively for each visit
Qn(x, a) & (1 - Qn a) aa((n( a) + (1 + b,), 1-1 +1,...t As result, at the end of round k, we have
a)) - af + 1, (h()))))
E of (ra(2, + ( + B²12 (8) (=
If we treat rh (1r, a) + Vi+t1 (1)+11)) as new estimate of the Qn a) induced by one visit within round k, then, all new samples are assigned with different weights f%2- Together with the weight assigned for the old estimate Q% a), it satisfies that (th + 1,t²)
+ Σi E1=0-141 0, 0,=00,111 =
Major Challenge in Federated Setting. The sequential updating rule in Equation 7 relies full accessibility of the trajectories to the agent, which is infeasible for the central server the feder- ated setting due to the high communication cost. Instead of sharing the raw data, in Algorithm 2 the local agents only send (o (z, a))-= the server. Since this is the sample average of the estimated values over all states visited after (ar, a, h)) it does not preserve the temporal structure of the trajectories. It thus becomes impossible for the server to infer the next state for each visit and sequentially update the global estimate as in Equation (7) in general.
Equal Weight Assignment for Q-estimate Aggregation. We overcome the aforementioned chal- lenge through a two-case design and new weight assignment for each visit.
In the first case, we have N (z, a) < ig- Equation (2) indicates that each client visits (z, a, h) at
most once, which implies that 7++1 in Equation (3) exactly Vi+11 (1)+ Thus, Equation (3) is
m..k
a sequential update and is the same as Equation (8). We also remark that the design of the first case
aims early-stage accuracy and shares similar technical motivations as Bai et al. (2019).
The second case shows the key difference between our algorithm and non-federated algorithms. Since the temporal structure is longer preserved, we cannot track the next state for given visit to (z, a, h). and it thus becomes impossible to assign a different weight to each new visit as in Equation (8) To resolve this issue, we choose to assign all visits with the same weight, while ensuring the total weight assigned to all visits unchanged, i.e.,
t"
(x, = a (z,
Σ
(ra(2, a) + V + 8hh /2. (z)
Oagg
L=th
which is equivalent to the updating rule in Equation
4 PERFORMANCE GUARANTEES
Next, we provide regret upper bound for FedQ-Hooffding as follows.
Theorem 4.1 (Regret Upper Bound for FedQ-Hoeffding). Les Ć (H)(H max } where in log(25 A(To HM)(1 + C)/p), log (TOSAAATTTHHHHMM0EH and p E (0,
P
Define b, Ht/tt Under Algorithms ] and 2 there exists positive constant 0 such that,
for any K E [Ko] and E (0, 1), with probability at least P.
Regret(T (T) 5 (VH*MMTS++ HSA(M #SAMM - 1IV + MH*SA+ H'SA(M (9)
7

---

Published as a conference paper at ICLR 2024
where T HE k= n² is the total number of steps in the first K rounds.
Theorem 4.1 indicates that the total regret scales O ((HH+MTSA) + OMMpoly(H, S, A) A)
The overhead term ((Mpoly(FF H, S, A)) is contributed by the (M) samples collected in the first stage, i.e., the burn-in cost. Such a burn-in cost is arguably inevitable in federated RL (e.g., Woo al.) (2023)) When M 1, our result recovers those in Jin et al. (2018) and Bai al. (2019). In the general federated setting, our algorithm enjoys a linear speedup in terms of M when T (MMpolyHH, SS, A)) and the first term dominates the burn-in cost.
Proof Sketch of Theorem 4. First, for any given (x. a, h) E S we assign a global visiting index i each local visit before starting the (k + 1)-th round, and denote the weight assigned the i-th visit as 6% with th = _xh (z, a). Specifically, for visits within the same round k', we index them by [N (Ir, a) +1: N a)] == IK' according to a pre-defined order. Then, for all visits within the first case, 0f equals to Pi.. and for all visits within round k in the second case, 0i ExEre ozx / aI,
The proof mainly consists of two major steps. Step is to bound the global estimation error 0 2% for each round k. Based on the recursive updating rule, we can show that, with high probability,
0 S 1 (x,a) (1(2, a) S 6G
Σ JEZ
(V (In21)5 + Bet,
th with 3e = Di Bi.b As shown in Lemma C.2 it suffices to bound - Ox where X, Vit (I141.5) -
an) = (x. a) Similar to the single-agent setting (Jin et al., 2018). (x,),= is martingale difference sequence. However, since our weight assignment for the 2-th visit depends on the total number of visits in the same round, which is determined after that round completes, {0;}]: 3: does not preserve the original martingale structure in (0: he Therefore, it necessitates novel approaches to bound the sum of non-martingale differences. We would like to emphasize that the techniques required to bound those non- mon-mattingale differences are fundamentally different from the commonly used techniques in federated learning (FL), which usually construct an "averaged parameter update path" and then bound each local term's "drift" from it. This is because such bounding techniques in FL rely on certain assumptions that do not exist in federated RL. Due the inherent randomness in the environment, even if the same policy is taken at all local agents, it may result in very different trajectories. Thus, it is hard to obtain an pasy-to-track "averaged parameter update path" in federated RI., or a tight bound on the local terms' drifts from such averaged parameter update path. We overcome this challenge by relating (0), }, with {0z, h- Instead of bounding the local drift 0j 6i. in each time step, we choose to group the "drift" terms based on the corresponding rounds and then leverage the round-wise equal weight assignment adopted in our algorithm to obtain a tight bound. The detailed analysis is elaborated in Lemma C.3
Built upon the estimation error bound obtained in Step 1, Step then utilizes the recursive Bellman equation to relate the total learning error among all agents in round k at step h with that at step + 1 (see Appendix C.3). b. which directly translates into a regret upper bound. The detailed proof
deferred to Appendix
Next, we discuss the communication cost under Algorithms and 2 as follows.
Theorem 4.2 (Communication Cost). Under Algorithms 7 and 2 total number of rounds must satisfy
for given number of steps T, the
T log H + 1)M log (1 220H(R+1)
HSA
K < max
+ HH +
Theorem 4.2 indicates that, when T is sufficiently large, K= 0 0 (MMFPsAoog((///))) /T/(MM))) Since the total number of communicated scalars is O(MSS) in each round, the total communication cost scales in ( 5 2 Alog(T/M)).
ZÔ ignores logarithmic factors.
8

---

Published as a conference paper at ICLR 2024
Due to the fact that the equality in Equation (2) is met for at least one agent, by the Pigeonhole principle, during the first rounds, there exists one tuple (æz, a, h, m) such that the equality in Equation (2) holds for at least (((/(HSAM)) rounds. In these rounds, as (I, a, h) are visited at least once in each round, at most (in) rounds belong to the first case. So, when K is large, there at least 92 ( (K//HHSAMM
Proof Sketch of Theorem 4.2
rounds in the second case and (2r, a)
Ö(N (1, a)) in these rounds. Thus we have H N (ar, a)/M, which is smaller than or equal to T, and roughly exponential in K when K is large. A detailed proof can be found in Appendix D
EXTENSION TO BERNSTEIN-TYPE ALGORITHM
The Bernstein-type algorithm differs from dence bound. Similar to the design in Jin et al. (2018), we define
on the construction of the upper confi-
c''min min { Hi H (Ir((, + H) + v SAS VSSH t
H
Bz a. h) =
(10)
in which > 0 a positive constant and (xx, a, h) is a variance estimator of X,s whose specific form is introduced in Appendix D FedQ-Bernstein then replaces 3 in Equation 3 and Equation (4) by 3 Ba (Iz a, h) - a (th + 1, thh ) (2, h). In terms of communication, during round k in addition all the quantities sent in Algorithm each agent m sends {or (n.n"(e (=, (x)))) the
central server where 14 m. (Ix a)
", m. (2,0) j=1 Vi++
(am44t))) )]
T[(a7 m.J.
0hh (m.kk))) (ar, a))-
The complete algorithm description can be found in Appendix E
As Ped@--Bernstein uses tighter upper confidence bounds compared with FedO-Hoeffding, it enjoys a reduced regret upper bound, as stated in Theorem 5.1 below.
Theorem 5.1 (Regret Upper Bound for PedQ-Bernsteing Let = 1/H with to lo. ATo + ( + C)/p, = log 2KGSAHCT7/H++4))444 and p E (0, 1). For
max( 41
y Algorithms 3 and in Appendix E with the upper confidence bound defined in Equation 10 there > 0 such that, for any K E [Kol. P E (0,1), 1), with probability at least
exists a constant
p.
Regret (T) s O M SA(M 1) HSA(M H)
+ H + &. + VISSAMT?
Here, T = H.J and J is the total number of of episodes generated by an agent in the first K rounds.
Theorem 5.1 improves the regret upper bound in Theorem 4.1 by a factor of VH, and also enjoys linear speedup in M compared with its single-agent counterparts (Jin et al., 2018 Bai et al. 2019) when T 2 (2MPllyy(HF H, S, A)) and the first term becomes the dominating term. Here Ω hides log factor that takes the form log" (MT
A))).
We also remark that the upper bound in Theorem 4.2 applies Fern-Bernstein as well. Since the amount of shared data is O(MHS) in each round for both algorithms, FedQ- -ernntetttten has the same order communication cost upper bound as FedQ-Hoeffding.
6 CONCLUSION
In this paper. we have developed model-free algorithms in federated reinforcement learning with provably linear regret speedup and logarithmic communication cost. More specifically, two feder- ated Q-learning algorithms
and FedQ- BelQ-Bernsteinn have been proposed, and we proved that they achieve regret of Ó(VH#SAMT) and O(VH'*SMMT) respectively with com- munication cost H A log(T/M)). Technically, our algorithm design features a novel equal weight assignment during global information aggregation, and we developed new approaches to characterizing the concentration properties for non- -orrtiniig differences, which could be of broader applications for other RL problems.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
The work of Z. Zheng and L. Xue was supported in part by the U.S. National Science Foundation under the grants DMS-1811552 DMS-1953189 and CCF-2007823. The work of F. Gao and J. Yang was supported in part by the U.S. National Science Foundation under the grants CNS-1956276, CNS-2003131, and CNS-21 14542.
IMPACT STATEMENT
This paper presents work whose goal is to advance the field of reinforcement learning. There are potential societal consequences of our work but none of them must be specifically highlighted in our opinion.
REPRODUCIBILITY
Numerical experiments this paper can be fully reproduced via the publicly available code
REFERENCES
Alekh Agarwal, Sham Kakade, and Lin Yang. Model-based reinforcement learning with a gener- ative model is minimax optimal. In Conference on Learning Theory, pp. 67-83, PMLR, 2020.
Mridul Agarwal, Bhargav Ganguly, and Vaneet Aggarwal. Communication efficient parallel rein- forcement learning. In Uncertainty in Artificial Intelligence, pp. 247-256. PMLR, 2021.
Shipra Agrawal and Randy Jia. Optimistic posterior sampling for reinforcement learning: worst- case regret bounds. Advances in Neural Information Processing Systems, 30, 2017.
1lge Akkaya, Marcin Andrychowicz, Maciek Chociej, Mateusz Litwin, Bob McGrew, Arthur Petron, Alex Paino, Matthias Plappert, Glenn Powell, Raphael Ribas, et al. Solving rubik's cube with robot hand. arXiv preprint arXiv: 1910.0910111111 13, 2019.
Mahmoud Assran, Joshua Romoff, Nicolas Ballas, Joelle Pineau, and Michael Rabbat. Gossip-based actor-learner architectures for deep reinforcement learning. Advances in Neural Information Pro- cessing Systems, 32, 2019.
Peter Auer, Thomas Jaksch, and Ronald Ortner. Near-optimal regret bounds for reinforcement learning. Advances in Neural Information Processing Systems, 21, 2008
Mohammad Gheshlaghi Azar, Ian Oshand, and Rémi Munos. Minimax regret bounds for reinforce- ment learning. In International Conference on Machine Learning, pp. 263-272. PMLR, 2017.
Yu Bai, Tengyang Xie. Nan Jiang, and Yu-Xiang Wang. Provably efficient q-learning with low switching cost, Advances Neural Information Processing Systems, 32, 2019.
Tianyi Chen, Kaiqing Zhang, Georgios B Giannakis, and Tamer Başar. Communication -ffficienn policy gradient methods for distributed reinforcement learning. IEEE Transactions Control of Network Systems, 9(2):917-929) 2021a.
Yiding Chen, Xuezhou Zhang, Kaiqing Zhang, Mengdi Wang, and Xiaojin Zhu. Byzantine-robust online and offline distributed reinforcement learning. In International Conference Artificial Intelligence and Statistics, pp. 3230-3268 PMLR, 2023.
Ziyi Chen, Yi Zhou, and Rongrong Chen. Multi-agent off-policy tde with near-optimal sample and communication complexit. In 2021 55th Asilomar Conference on Signals, Systems, and Computers, pp. 504-508. IEEE, 2021b.
Ziyi Chen, Yi Zhou, Rong-Rong Chen, and Shaofeng Zou. Sample and communication decentralized actor-critic algorithms with finite-time analysis. International Conference on Machine Learning, pp. 7794--8334 PMLR, 2022.
hhttps://openeee ew, net hwt.://www................ooo.en ay naterial
10

---

Published as a conference paper at ICLR 2024
Christoph Dann, Lihong Li, Wei Wei, and Emma Brunskill. Policy certificates: Towards account- able reinforcement learning. In International Conference on Machine Learning, pp. 1507-1516. PMLR. 2019.
Thinh Doan, Siva Maguluri, and Justin Romberg. Finite-time analysis of distributed td (0) with linear function approximation on multi-agent reinforcement learning. In International Conference on Machine Learning, pp. 1635.1635. PMLR, 2019.
Thinh T Doan, Siva Theja Maguluri, and Justin Romberg. Finite-time performance of distributed temporal-difference learning with linear function approximation. SIAM Journal on Mathematics of Data Science, 3(1):298-324) 2021.
Abhimanyu Dubey and Alex Pentland. Private and Byzantine-proof cooperative decision-making. arXiv preprint arXiv:2205. 220.:2244444 2022.
Abhimanyu Dubey and AlexSandy' Pentland. Differentially-prine privatte federated linear bandits. Ad- vances in Neural Information Processing Systems, 33:6003-600 6014, 2020.
Lasse Espeholt, Hubert Soyer, Remi Munos, Karen Simonyan, Vlad Mnih, Tom Ward, Yotam Doron, Vlad Firoiu, Tim Harley, lain Dunning, et Impala: Scalable distributed deep-rl with im- portance weighted actor-leamer architectures. In International Conference on Machine Learning, pp. 1407-1416. PMLR, 2018.
Flint Xiaofeng Fan, Yining Ma. Zhongxiang Dai, Wei Jing. Cheston Tan, and Bryan Kian Hsiang Low. Fault-tolerant federated reinforcement learning with theoretical guarantee. Advances in Neural Information Processing Systems, 34: 1407-0101 2021.
Flint Xiaofeng Fan, Yining Ma, Zhongxiang Dai, Cheston Tan, and Bryan Kian Hsiang Low. Fedhql: Federated heterogeneous q-learning. In Proceedingg of the 2023 International Conference on Autonomous Agents and Multiagent Systems, pp. 28 2810-2812, 2023.
Zijun Gao, Yanjun Han, Zhimei Ren, and Zhengqing Zhou. Batched multi-armed bandits problem. Advances in Neural Information Processing Systems, 32, 2019.
Shixiang Gu, Ethan Holly. Timothy Lillicrap. and Sergey Levine. Deep reinforcement learning for robotic manipulation with asynchronous off-polic updates. In 2017 IEEE International Confer- ence on Robotics and Automation (ICRA), pp. 3389-3396 IEEE, 2017.
Zhaohan Guo and Emma Brunskill. Concurrent pac rl. In Proceedings of the AAAI Conference on
Artificial Intelligence, volume 29, pp. 2624-2630, 2015.
Jiafan He, Tianhao Wang, Yifei Min, and Quanquan Gu. A simple and provably efficient algorithm for asynchronous federated contextual linear bandits. urXiv preprint arXiv:2207.08 106,, 2022.
Ruiquan Huang, Weiqiang Wu, Jing Yang, and Cong Shen. Federated linear contextual bandits.
Advances in Neural Information Processing Systems, 34:27057- 2021.
Ruiquan Huang, Huanyu Zhang, Luca Melis, Milan Shen, Meisam Hejazinia, and Jing Yang. Fed- crated linear contextual bandits with user-level differential privacy. International Conference on Machine Learning, pp. 14060-14095. PMLR, 2023.
Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael Jordan. Is q-learning provably effi- cient? Advances in Neural Information Processing Systems, 31, 2018.
Hao Jin, Yang Peng, Wenhao Yang, Shusen Wang, and Zhihua Zhang. Federated reinforcement learning with environment heterogeneity. In International Conference on Artificial Intelligence and Statistics, pp. 18-37. PMLR, 2022.
Sham Kakade, Mengdi Wang, and Lin F Yang. Variance reduction methods for sublinear reinforce- ment learning. arXiv preprint a 1802.09/844 2018
Dmitry Kalashnikov, Alex Irpan, Peter Pastor, Julian Ibarz, Alexander Herzog, Eric Jang, Deirdre Quillen, Ethan Holly, Mrinal Kalakrishnan, Vincent Vanhoucke, et al. Qt-opt: Scalable deep reinforcement learning for vision-baat based robotic manipulation. arXiv preprint arXiv: 10293, 2018.
11

---

Published as a conference paper at ICLR 2024
Sajad Khodadadian, Pranay Sharma, Gauri Joshi, and Siva Theja Maguluri. Federated reinforcement learning: Linear speedup under markovian sampling. In International Conference on Machine Learning. pp. 10997-11057. PMLR, 2022.
Jens Kober, J Andrew Bagnell, and Jan Peters. Reinforcement learning in robotics: A survey, The International Journal Robotics Research, (2(11))1233-122 1274,, 2013.
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, 2022.
Fengjiao Li, Xingyu Zhou, and Bo Ji. Differentially private linear bandits with partial distributed feedback. In 2022 20th International Symposium on Modeling and Optimization in Mobile, Ad hoc, and Wireless Networks (WiOpt), pp. 41-48. IEEE, 2022a.
Gen Li, Laixi Shi, Yuxin Chen, Yuantao Gu, and Yuejie Chi. Breaking the sample complexity barrier to regret-optimal model-free reinforcement learning. Advances in Neural Information Processing Systems, 34:17762-1777, 2021.
Tan Li, Linqi Song, and Christina Fragouli. Federated recommendation system via differential privacy. In 2020 IEEE International Symposium on Information Theory (ISIT), pp. 2592-2597. IEEE, 2020.
Wenjie Li, Qifan Song, Jean Honorio, and Guang Lin. Federated x-armed bandit. arXiv preprint arXiv:2205.1 15268, 2022b.
Rui Liu and Alex Olshevsky. Distributed td (0) with almost no communication. IEEE Control Systems Letters, 2023.
Shicheng Liu and Minghui Zhu. Distributed inverse constrained reinforcement learning for multi-
agent systems. Advances in Neural Information Processing Systems,
2022.
Shicheng Liu and Minghui Zhu. Learning multi-agent behaviors from distributed and streaming demonstrations. Advances Neural Information Processing Systems, 36, 2024.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication-effan efficient learning of deep networks from decentralized data. Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, volume 54, pp. 1273- 1282. PMLR, 2017.
Pierre Ménard, Omar Darwiche Domingues, Xuedong Shang, and Michal Valko. Ucb momen- tum glearniig: Correcting the bias without forgetting. In International Conference on Machine Learning, pp. 7609-7618. PMLR, 2021.
Volodymyr Mnih Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukcuogiu. Asynchronous methods for deep reinforcement learning. International Conference on Machine Learning, pp. 1928-1937. PMLR, 2016.
Arun Nair, Praveen Srinivasan, Sam Blackwell, Cagdas Alcicek, Rory Fearon, Alessandro De Maria, Vedavyas Panneershelvam, Mustafa Suleyman, Charles Beattie, Stig Petersen, et al. Massively parallel methods for deep reinforeement learning. arXiv preprint 1507.4250. 2015.
Vianney Perchet, Philippe Rigollet, Sylvain Chassang, and Erik Snowberg. Batched bandit prob- lems. The Annals of Statistics, 44(2):660 681, 2016.
Dan Qiao, Ming Yin, Ming Min, and Yu- Yu-Xiang Wang. Sample-efficient reinforcement learning with loglog (t) switching cost. In International Conference Machine Learning, pp. 18031-18061. PMLR, 2022.
Han Shen, Kaiqing Zhang, Mingyi Hong, and Tianyi Chen. Towards understanding asynchronous advantage actor-critic: Convergence and linear speedup. IEEE Transactions on Signal Processing, 71:2579-2591 2023a.
12

---

Published as a conference paper at ICLR 2024
Han Shen, Kaiqing Zhang, Mingyi Hong, and Tianyi Chen. Towards understanding asynchronous advantage actor-critic: Convergence and linear speedup. IEEE Transactions on Signal Processing, 2023b.
Chengshuai Shi and Cong Shen. Federated multi-armed bandits. In Proceedings of the AAAI Con- ference on Artificial Intelligence, volume 35, pp. 9603-9611, 2021.
Chengshuai Shi, Cong Shen, and Jing Yang. Federated multi-armed bandits with personalization. In Proceedings of the 24rd International Conference on Artificial Intelligence and Statisties (AIS- TATS), April 2021.
David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Pannecrshelvam, Mare Lanctot, et al. Mastering the game of go with deep neural networks and tree search. Nature, 529(7587):484 489, 2016.
David Silver, Thomas Hubert, Julian Schrittwieser, Toannis Antonoglou, Matthew Lai, Arthur Guez, Mare Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, et al. Mastering chess and shogi by self-play with general reinforcement learning algorithm. arXiv preprint arXiv: 171220181. 2017.
David Silver, Thomas Hubert, Julian Schrittwieser, loannis Antonoglou, Matthew Lai, Arthur Guez, Mare Lanetot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, et al. A general reinforcement learning algorithm that masters chess, shogi, and go through self- play. Science, 362(6419): 1140- 1144, 2018.
Jun Sun, Gang Wang, Georgios B Giannakis, Qinmin Yang, and Zaiyue Yang. Finite-time analysis of decentralized temporal-differene learning with linear function approximation. In International Conference on Artificial Intelligence and Statistics, pp. 4485 4495. PMLR, 2020.
Sutton and A Barto. Reinforcement Learning: An Introduction. MIT Press, 2018.
Oriol Vinyals, Igor Babuschkin, Wojeiech M Czamecki, Michaël Mathieu, Andrew Dudzik, Juny- oung Chung, David H Choi, Richard Powell, Timo Ewalds, Petko Georgiev, et Grandmaster level in starcraft ii using multi-agent reinforcement learning. Nature, 575(7782):350-334 2019,
Hoi-To Wai. On the convergence of consensus algorithms with markovian noise and gradient bias. In 2020 59th IEEE Conference on Decision and Control (CDC), pp. 4897-4902. IEEE, 2020.
Chi-Hua Wang, Wenjie Li, Guang Cheng, and Guang Lin, Federated online sparse decision making. arXiv preprint 1:X.::2202..344: 2022.
Gang Wang, Songtao Lu, Georgios Giannakis, Gerald Tesauro, and Jian Sun. Decentralized td tracking with linear function approximation and its finite-time analysis. Advances in Neural In- formation Processing Systems, 33:13762-13772 2020a.
Tianhao Wang, Dongruo Zhou, and Quanquan Gu. Provably efficient reinforcement learning with linear function approximation under adaptivity constraints. Advances in Neural Information Pro- cessing Systems, 34: 1454444--33 2021.
Yuanhao Wang. Jiachen Hu, Xiaoyu Chen, and Liwei Wang. Distributed bandit learning: Near- optimal regret with efficient communication. In International Conference Learning Represen- tations, 2020b.
C. J. C. H. Watkins. Learning Delayed Rewards. PhD thesis, King's College, Oxford, 1989.
Jiin Woo, Gauri Joshi, and Yuejie Chi. The blessing of heterogeneity in federated q-learning: Linear speedup and beyond. In International Conference on Machine Learning, pp- 37157-37216, 2023.
Zhaoxian Wu, Han Shen, Tianyi Chen, and Qing Ling. Bezinttn decentralized policy evaluation with linear function approximation. IEEE Transactions Signal Processing, 69: 3839-3853, 2021.
Kunhe Yang, Lin Yang, and Simon Du. Q-learning with logarithmic regret. In International Con- ference Artificial Intelligence and Statistics, pp. 1576-1584, PMLR, 2021.
13

---

Published as a conference paper at ICLR 2024
Ekim Yurtsever, Jacob Lambert, Alexander Carballo, and Kazuya Takeda. A survey of autonomous driving: Common practices and emerging technologies. IEEE Access, 8:58443-5888 0884493-8469, 2020.
Andrea Zanette and Emma Brunskill. Tighter problem-dependent regret bounds in reinforcement learning without domain knowledge using value function bounds. In International Conference on Machine Learning, pp. 7304-7312 PMLR, 2019.
Sihan Zeng, Thinh T Doan, and Justin Romberg. Finite-time analysis of decentralized stochas- tic approximation with applications in multi-agent and multi-task learning. In 202/ 60th IEEE Conference on Decision and Control (CDC), pp. 2641-2646. IEEE, 2021.
Zihan Zhang, Yuan Zhou, and Xiangyang Ji. Almost optimal model-free reinforcement learning via reference-advantage decomposition. Advances in Neural Information Processing Systems, 33: 15198 15207, 2020.
Zihan Zhang, Xiangyang Ji, and Simon Du Is reinforcement learning more difficult than bandits? near-optimal algorithm escaping the curse of horizon. In Conference on Learning Theory, pp. 4528 4531. PMLR, 2021.
Zihan Zhang, Yuhang Jiang, Yuan Zhou, and Xiangyang Ji. Near-optimal regret bounds for multi- batch reinforcement learning. Advances in Neural Information Processing Systems, 35:24586- 24596, 2022.
Zihan Zhang, Yuxin Chen, Jason D Lee, and Simon Du. Settling the sample complexity of online reinforcement learning. arXiv preprint arXiv:2307.13586 2023.
Runlong Zhou, Zhang Zihan, and Simon Shaolei Du. Sharp variance- denendden bounds in reinforce- ment learning: Best of both worlds in stochastic and deterministic environments. In International Conference on Machine Learning, pp. 22878-42911 PMIR, 2023.
Xingyu Zhou and Sayak Ray Chowdhury. differentially private federated linear contextual ban- dits. arXiv preprint 20X2::2302.13945, 2023.
Zhaowei Zhu, Jingxuan Zhu, Ji Liu, and Yang Liu. Federated bandit: A gossiping approach. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 5(1):1-29, Feb 2021. ISSN 1249, doi: 10.1145/3447380. URL http:// doi org. 3447380
14

---

Published as a conference paper at ICLR 2024
A RELATED WORKS
Single-agent episodic MDPs. Significant contributions have been made in both model-based and model-free frameworks. In the model--asee category, series of algorithms have been proposed by Auer et al. (2008), Agrawal & Jia (017)) Azar et al. (2017). Kakade et al. (2018), Agarwal et al. (2020), Dann et al. (2019), /anette & Brunskill (2019) 9). and /Zhang et al. (2021). with more
recent contributions from Zhou et al. (2023) and Zhang et al. (2023). Notably, Zhang et al. (2023)
proved that modified version of MVP (proposed by Zhang et al. (202) achieves a regret of
δ min| ( SAHTT, TT) which matches the minimax lower bound. Within the model-free frame-
work, Jin al.
2018) proposed a Q-learning with UCB exploration algorithm, achieving regret of SSH3T which has been advanced further by Yang et al. (2021), Zhang al. (2020), Li
Ö
et al. 2021 and Ménard et al. (021). The latter three have introduced algorithms that achieve
minimax regret of Ô (VSAHTT)
Federated and distributed RL. Existing literature on federated and distributed RL algorithms sheds light on different aspects. Guo & Brunskill (2015) showed that applying concurrent RL to identical MDPs can linearly speed up sample complexity. Agarwal et al. (2021) proposed parallel RL algorithm with low communication cost. Jin et al. (2022) Khodadadian et al. (2022). Fan et al.
(2023 and Woo et al. (2023) investigated federated Q-learning algorithms in different settings. Fan et al. 2021). Wu et al. (2021) and Chen et al. (2023) focused on robustness. Particularly, Chen al. (202)) proposed algorithms in both offline and online settings, obtaining near-optimal sample
complexities and achieving a superior robustness guarantee. Doan et al. (2019), Doan et al. (202
Chen et al. (2021b). Sun et al. (2020), Wai (2020). Wang al. (2020a). Zeng et al. (2021) and Liu & Olshevsky (2023) analyzed the convergence of decentralized temporal difference algorithms, Fan
caaauunication-fffciiee policy gradient algorithms. Shen et al. (023b), Shen et al. (2023a) and Chen et al. (2022) have analyzed the convergence of distributed actor-critic algorithms. Assran et al. (2019), Espeholt et al. (201)) and Mnih et al.) (2016)
al. (2021) and Chen al.] (2021a) studied
explored federated actor-learner architectures. Liu & Zhu (2022) and Liu & 7hu (2024) explored
distributed inverse reinforcement learning.
RL with low switching cost and batched RL. Research in RL with low-switching cost aims to minimize the number of policy switching while maintaining comparable regret bounds to its fully adaptive counterparts and can be applied to federated RL. In batched RL (erccht et al.) (2016), Gao et al. (2019). the agent sets the number of batches and length of each batch upfront, aiming for fewer batches and lower regret. |Bai et al. (20T9) first introduced the problem of RL with low- switching cost and proposed Q-learning algorithm with lazy update, achieving ASSAH3) log T) switching costs. This work was advanced by Zhang et al. (2020), which improved the regret upper bound. Besides, |Wang al.] (202T) studied the problem of RL under the adaptivity constraint. Recently, Qiao et al. (2022) proposed a model-based algorithm with Ölog log T') switching costs. Zhang et al. (2022) proposed a batched RL algorithm that is well-suited for the federated setting.
Federated/diistribute bandits. Federated bandits with low communication costs have been studied extensively recently in the literature Wang et al. | (2020b); Li & Wang (2022); Shi & Shen (2021); I); Shi
al. (202T); Huang et al. (2021): WWang al. (2022); x et al. (2022); )::2):: Li al. (2022b). (Sh & Shen
(2021) and Shi et al. (2021) investigated efficient clivnt-server communication and coordination
protocols for federated MAB without and with personalization, respectively. |Wang et al. (2020b)
investigated communication-efficentt distributed linear bandits, while Huang et al. (2021) studied
federated linear contextual bandits. Li & Wang (022) focused on the asynchronous communication
protocol.
When data privacy explicitly considered, Li et al. (000 Zhu et al. (2021) studied federated
bandits with item-level differential privacy (DP) guarantee. Dubey & Pentland (2022) considered
private and byzantine-pros proof cooperative decision making in multi-armed bandits. Dubey & Pentland
2020); Zhou & Chowdhury (202)) considered the linear contextual bandit model with joint DP guarantee. Huang et al. (2023) recently investigated linear contextual bandits under user-level DP
constraints. Private distributed bandits with partial feedhack was also studied in Li al. 2022a).
15

---

Published as a conference paper at ICLR 2024
B AUXILIARY LEMMAS
In this section, we introduce some useful lemmas which will be used in the proofs. Before starting, we describe the global indexing mechanism mentioned in Section 4 Global visiting indices i 1,2... are assigned, based on the chronological order, to the visits of any given (z, a. h) E S x A x [H]. With this, we can establish a map between the global visiting index i, and k. m. where is the round index, is the agent index and j is the episode index for given round and given agent. For (z, a, h), we define functions that recover k, m, from as k2 (1; x. a), m x a), jn x, a). When there is no ambiguity, we will use the simplified notations k² .mm :J'. The visiting indices are utilized to construct a sequence, ensuring that quantities with smaller indices are observed prior to those with larger indices. Under the synchronization and zero-latency assumption, we have the following formulas for m', m',k',J" K'.
(i; (i;
(1; a) = sup { E N+ : (N(, <i),
j-1
dn (1; = sup j jEN+:
ΣΣ j'=1m=1
(c, -
(x (m
,0 ['m < N 1ala
m-1
m)(tsx,a) sup
m N
Σ
ll (x,
(xh
m² Mit mn 1o sttst)
m/=1
1'11
<i- Ni (z,
ΣΣ j'=lm=l
E (z,
(a aa m amm.ke 1m
We also introduce new notation / = .T that represents the total number of samples generated by all the agents.
Next, we begin to introduce the lemmas. First, Lemma B.1 establishee some relationships between some quantities used in Algorithms [ [
Lemma B.I. Denote Č = 1/(H(H - 1)). The following relationships hold for both algorithms.
(a) K Kg.
(b) NW (z, S To/H.
(c) For any (z, a, h. K) E S x Ax H x [K]
we have
m.k (x, a) < max { 1, M n
CN
vm E [M].
(11)
and
(x a) I max[M, CN. a)).
(12)
2 io.
(d) For any (z, a) S Ax [II K
M.
(e) Í < (1+ H.M
Proof of Lemma B. | (a)-(c) are obvious given Algorithms T and (d) and (e) can be directly obtained from (b) and (c).
Next, Lemma B.2 provides some properties about fj'..
Lemma B.2. (Lemma 4.1 in Jin et al. (2018) and beyond) The following properties hold for all I E N4 for both algorithms.
16

---

Published as a conference paper at ICLR 2024
(a) 1/v2 z Ei= 0i/Vi - 2/ Vt, which implies that Be [2c/ H31/t, 4e H31/t), Vt N+.
(b) max 0 - 2
(c) Ei= (0i)² 24/t.
(d) EeS 11= 1/H
(e) For any E N+ and E [t]- {t), 0,t1 18, = 1+ H/1
(f) For both algorithms, for any N+ and (I,a,h) E A [H], if i,,82 [t], kn (i, F. 2i, a)) = (12, x. a) and No (11,0)) (x, a) 2 in we have that 07: /0 S exp(1/H).
Proof of Lemma B.2 (a)-(c) are obvious based on 0 definition and Lemma 4.1 in Jin et al. 2018 For (f, denoting to (/ .,,)) (I, a) and 1 = N- (r,))) (x, a), based on (e), we have
4-1
0 10/2 s 0 10
II +/11). t'=ta
Based on (c) in Lemma B.1 we further have that
1-1
II ((t) s (1 H/to) (1+ S (tx - to)/to) s exp(1/HH.
Next, we rigorously define the weights 0 mentioned in Section
For any (æ, h K*) k²) E ExXAx
[H] x [K]. we let t = =Nn (zz, a) and E Ut0). Letting t'
NE (x, a) and t" = N + (z,a),
we denote
(z, a, h) = o/ io] + 1 1 (t' + 1,t")
-1 at" + 1, 2 io).
and we will use the simplified notation 0j when there no ambiguity. Lemma B.3 provides proper- ties of 0 and its relationship with 02.
Lemma B.3. The following relationships hold for any (x, a, h K') E S x x [M] x [K] with t N (xr, a) for both algorithms.
(a) (;(x,a,)) (x, (1' + 1,1) with 1' 1 (2),
(b) For any i, [t), if kn (61, x. a) kn, v, a) and (1116112,00 (I,, a) to, we have that
07 (x, a.h) = 072 (xt, a, h).
(c) For any K' < K', we have that
(a)o)
No. Nk'+ (ara)
(x,
0f
#= NK (a,a)+1
#1 == (1,0)+1
which indicates that
Σ 0 1[t > 0).
1=1
(d) For any E [1], when N ( (x, a) 2 io, we have that
(1 + H/(1 N:)) < 0 < (1 + H/(1 + -.)
in which N, Nyha (xr, a) and n; n
An (i.x,a) (x,
17

---

Published as a conference paper at ICLR 2024
(e) For any E [1} when N Nalleiahh (2,, a) 2 io, we have that
0//0 - exp(1/H).
Proof of Lemma B.3 (a)-(C) can be obtained directly through the definition of 0j. Next, prove
(d) and (e). Denote to = N (x. a) and & = Nzz N- (a, a). By (c) and (e) in
Lemma B.2 we have that 022 /0 I 0 I 02 /0/. Then, (d) can be proved by noticing that 0 % < (1 + H/(1+ + NN))
This implies that (e) holds because of (c) in Lemma B.
C PROOF OF THEOREM 4.
C.1 ROBUSTNESS AGAINST ASYNCHRONIZATION
In this subsection, we discuss a more general situation for Algorithms and where agent m generates n episodes during round We longer assume that m. the same value n² for different clients. The difference can be caused by latency (the time gap between an agent sending an abortion signal and other agents receiving the signal) and asynchronization (the heterogeneity among clients on the computation speed and process of collecting trajectories). In this case, for K rounds, the total number of samples generated by all the clients is
M
H
n
m.k
A
m==1
Thus, we generalize the notation T T/M, which characterizes the mean number of samples generated by an agent. Accordingly, the definition of (T) can be generalized
Regret(T) = Σ
(x - VI (off.k.))
j=1
Similarly, the definitions of mi m.k (xxaa) Nmm (x, a), m.kk (xx a) are also generalized by replacing Σ/ with m プド=1
We note that Algorithms I and naturally accommodate such asynchronicity. Therefore, in the following analysis of the regret, we adopt the general notation na. However, for the proof of Theorem 4.2 pertaining to communication, we will maintain the synchronization assumption that
m. vm E [M).
C.2 BOUNDS ON Q Q7,
Lemma C.I. For Algorithms and 2 there exists positive constant 0 such that, for any
p E (0, 1), the following relationship holds for all (æ, a, h, K') e Ax [H] x [K] with probability
at least p.
0 Q (x, a) (, < 0u1
0i(Vi
Vitt) M. Br,
(13)
in which i NKK (z)
We first provide Lemma to formally state Equation 14p and Equation (5) which establish the relationship between Q and Q The proof is the same as the proof of Equation (4.3) in Jin et al. (001)).
18

---

Published as a conference paper at ICLR 2024
Lemma C.2. For the Hoeffdingg type Algorithms Land for all
h, (x, E ESxAx [H] x [K],
denoting i NK (x, a), we have
Q (x, H.
0 (ra(z,a) + ( 3) + Σ bibs
(14)
i=1
Q)( Q
0 (r)( (PraVital (2) Bur n. + b. Vitti
Furthermore, we have
(Qf (1) 0. (H ()( Σ
0 (Bzza,hii ax Viit1
@i(Vi h+1 Vo++1)
ml M
0gbs:
(15)
02 (H (2(2, a)) + (Q - (x) =
0 (Bz Ex,,,
in which
Bz V Bur,a, h+ (3n+1) = E. ( (2r, a)]
B :i:t1 = B Vi (Ih+1) (x s').
With this lemma, we derive probabilistic upper bound for Ei= 0xX.1 with X; = (Ez,ahs b, Vi+1 Lemma C.3
Lemma C.3. There exists co > such that, for any p E (0, 1), with probability at least - ps the
following relationship holds for all (I,, a,, K') E S A x [H] x [K] with t NoK (x:
Σ OE V (*++1) S H0V/131/L
(16)
Proof. For a given az, h) E S x Ax [H]. denote X1(I, a, h) = (Ln Ex,,,,) (xx41))
When there is no ambiguity, we use the simplified notation X; = X,(æ, h). We know that {X,] is a sequence of martingale differences with [X, < H. We decompose the summation
as follows:
0 > (0) X2)
Note that & To/H. H.
First, we focus on the first term. By Azema-Hoefiding Inequality, for any given (I, a, h) E Ax [H] and a given t' E N+, for any p (0, 1). with probability p, there exists numerical constant
C1 such that
c'
1' (0)))
Σ
Xi
S SOHH
Σ
log
2 p
i=1
which indicates that D 1 0f X;
< c1 V2V
/ (H3/1) log based on (c) in Lemma B.2
By considering all the possible combinations (z, a, h, t') E S x Ax [H] x To H. with a union bound and the realization of t t'. we have, for any p E (0, with at probability at least 1 P, the following relationship holds simultancously for all (x, a, h, K') e S A x [H] [K]:
Σ exx < e1 V2
(H3 /
log
2SAT.
<
C1
1/H
/2
19

---

Published as a conference paper at ICLR 2024
We then focus the second term Σ -0) For any given (z, k,),))))) E S [K], we consider the part with samples generated by the kg-th round, which is
Lg Σ (0) 1=
02 X,,,
in which l2 No (z, a) + 1, ta N
We can control the second term by controlling
Ex (0t, oi Xx for all Kg E [K].
We have
2 x
II
K' Σ Σ
11
(1
ar
fs Σ
0%
X
(17)
L''=t++1
To begin with, we prove that there exists a numerical constant cg such that
fa
Σ ei 8² C3
Σ
(18)
t'mt2
This relationship obviously holds when N₁ (3r, have
io LHS 0. When No (x,
a) 2 in.
t/ (0
Is
(2 12)²
H11s 12)
52
(0%
0
t2
12
where the first inequality comes from (d) in Lemma B.3 and the second one comes from (f) in Lemma B.2
We also have that
Hit3 - 12)3/2
12)--12)3/
H(ta 1/)
(ts (t3-ta (2)0 =0 (
0/3
=0
Vl2
where the second relationship comes from (f) in Lemma B.2 This completes the proof of Equa- tion (18).
Next, we proceed with discussions conditioning on all the information before starting the ky-th round, which means that N (z, a) and te can be treated constants. If NV (I, io. this quantity is equal to O. Otherwise, given any l/3 2 l2 and i E [12, (3), we denote
ac)
0g
II (1
/ttss t2 1),
t'=t
Therefore, in the expression E (0:g 02g X,, we can treat {X1z, Xtzt1 ... Xg.} as martingale differences and f7,8 and 0rg as constants. Hence, by azuma-Hoeffdiin Incquality, there exists a positive numerical constant 02 such that, for any p E (0, 1), with probability at least 1
f (drg 0 X I CoH
2 1 log p v=12
(drs - 022
By considering all possible values of t/2 with union bound, we have that with probability at least
1 p, the following relationship holds simultaneously for any 12 < < ta +1+ (1+ M
2(To/H H (1 + C
Σ (0.g
xx
Xx,
< H log
Σ
(0gg 0 )2
P
1=62
20

---

Published as a conference paper at ICLR 2024
So, noticing that Bug 8% when t's ty and E [t2, and applying Equation (88) for any he N+ and any p E (0, 1), with probability least 1 p.
we have that,
Σ 0o xx)) S C203 H log 2(To/ H + M) C9
02
Pig/Vi.
p
We apply the union bound and claim that for any p E (0, 1), the following relationship holds with probability least 1 for all (I, a, ks) E S A [H] [Ko].
ta Σ i=
2SAH Ko (To/H H + M)(1 + C) tg
0x
S scccsHl log
Σ i=t2
o
/vii
p
= c2call V
Σ Ll/Vi.
Under this event, with Equation
we have that
Σ 00 0;)x 8202 Σ
V500/Vi.
(19)
==1
By (a) in Lemma B.2 we have Ei=10i/V 0 S V4fl. Combining the results for the two terms completes the proot.
Finally, we provide the proof for Lemma C.I
Proof of Lemma C.7 We pick c = co such that the event in Lemma
C holds. Under the event
given in Lemma and noting Equation (15). claim the conclusion by using the same proof as that for Lemma 4.3 in Jin et al. (2018).
C.3 PROOF OF THEOREM 4.1
Having proved Lemma C.I we turn our attention to demonstrating the remaining parts of the proof. We use mik to denote the number of episodes by agent in round k.
We first provide some additional notations. Define
M
n
8%
V Vir" (o.t.
j=1
x2 m.
(V Vi) (x m. vh E [H + 1),
which 8/411 = 0b++1
0. We also define
M n mm
sh = Σ
Σ (P IP) (Vitz Vitts) (smided mm hel [H]
m=1 j=1
with ch+1 = 0. Here,
(P) (Vitz virta) (1 (miikis a miskss E (V(iitz - viita) (zm ( mis. a mm.k))))
and
(P) (Vit1 vitis (z ma a m.skss = (Vitz - vitta) (omilt
We first provide Lemma related ch
21

---

Published as a conference paper at ICLR 2024
Lemma C.4. There exists numerical constant Cs at least - p.
O such that, for any p (0, 1), with probability
K
H
Σ
Ch
ok Sh+1
S
ScgHT..
(20)
h=1
where Ch -xp(3(h-1)/41)
m.j. Proof. Denote V(m, k i,) = Cn(P - P) (ii+i Vi (2h , ,a mi.k.) and use Em,k,jjh as simplified notation for Σ Em= E m.
H-1 The quantity of interest can be rewritten as
Emjiihh (mm, j, h), with (V k, j, h)] (HH) as Ch S exp(3).
Let (ii be the i-th term in the summation that contains 7(H 1)/H terms, in which the order follows "round first, episode second, step third, agent fourth" rule. Then the sequence (i) a martingale difference. By Azuma-Hoeffding Inequality, for any p E (0,1) and f E N4. with probability least 1 p.
2 -
Σ V
0
H
log
p
Then by applying a union bound over t E [1 + C)To + HM and knowing that T(H 1)/H s
(1 + C) + HM due to (c) in Lemma B.1 have that, for any p E 1), with probability at least 1 - p.
K
H
((H-1)/H
Σ
C.
Σ
v(1)
s SO(HVTI).
Sh+1
i=1
This completes the proof.
Noticing that (eg < Ex= of due to (Tgret(T) = Ek of
-Σ
k= of and of 2 0 shown
in Equation 13 we attempt establish probability upper bound for Σk 04. First, have
M n mad
M
n m.
Qhh
Q2)
aah k.s.
Σ
Σ
(Qh -0%% (2 ah mnik))
(21)
which holds because VØ"" (2)t. = Q (2 oa am and
ví 22) (..kk.))
S max Qh (amiks, .d = =Qu: (2 mi m..ks a'EAA
Next, we attempt to bound the terms in RHS of Equation (1 separately. Our discussions are m.kj based on the events outlined in Lemma C.1 For any given h, denote pmm N (am a m.kk) and the corresponding k. m.j (round index, agent index, and episode index) for the i-th global visiting for (x) R..j. m.k.J. h) are k.m.k.j m.k.j ...... = 1,2... ... mm.... For the first term, due ax
i , 1
to Equation 13 we have
M
12
m.kkj
an
1=1
M m.k
M n mikk piides
H +
0
(V++1
h+l
M n
(22)
1=1
22

---

Published as a conference paper at ICLR 2024
For the second term, due to Equation
I..
n m.kk
Σ Qh @h (ar (x
an ani.k h++1 2h+1 + Eh+1
(23)
Next, we try to find some bounds related to Σ 8% For notation simplicity, we use Em,k. to represent Appendix
Dmm We can prove the following relationships with details referred to
m== 25=1
E
80 h
H MHSA.
(24)
m.kjj
K (1 S 6/H
Σ
0f mm.s ki h+1
(m,kk))
Σ
Pht + 5OH1 1)).
m,k. 1=1
(25)
K
M
m.kk n
B m. 4/
I HRVTTS S 11AM-1
(26)
R=
m==
Combining Equations
22 to 26
we have that for any h [H].
k
K
K
1x)(3/11)
h+1
h++
k=1
k=1
k=1
k=1
1=1
0 HAISA + SA(M H) + MHSA H -1))
Noticing that t 2 0% A(h, k)) [H] [K] due to the optimality of x and cxp(3/H) 0(1),
by recursions on 1,2. H, we have
K
H-1
K
Cp
Shtz
hm1
km
(V HHHTSAA HSA(M- 110 MH MAASSAAASSSSSSSSSSSSSS
+0
in which Cp exp(3(h 1). With Lemma
C.4
we can also show that, with high probability,
K
H
Σ
C
ck Sh-1
SO(HVT.)
(27)
1=1
h=1
This indicates that 8 -OA-WAAAAAAA--A-----F----A---SS-
With these discussions, we have already shown that, under the intersection of events given Lemma and Lemma
C.4
K
Regret(T")
S
1=1
0
HSA-MMMIMYEEF--- H-SA(M-1)M) 11)
By replacing for the events in Lemma C.1 and Lemma C.4 with p/2, we finish the proof.
C.4 PROOFS OF EQUATIONS 24 TO 26
In this subsection, we try to give bounds the terms in RHS of Equation 21 separately. We make
discussions based on the intersection of events given in Lemma C.I and Lemma C.4 Under these
events, we have already shown that Equation (22). Equation (2) and Equation 27 hold. So, we
will provide the proof by establishing Equations 24
26
23

---

Published as a conference paper at ICLR 2024
Proof of Equation 24 First, we note that
60
H m.k..
H
H
1t =0]
For each (2r, a, h) E S x we consider all the rounds indexed as 0 < k1 < h2 < ... satisfying the condition n (2. a) > O. Here, k,s are simplified notations for functions of (s, a, h), and we use the simplified notations when there is no ambiguity and the stated meaning of these notations is applicable only to the proof of Equation 22 So,
Σ k.
Ti = 0] R
K.J. an m..kj.) = (x, a)] S n (c. a).
As Noh (x. a) = O, due to Equation
12
we have ni (I, a) S M. Therefore,
Σ 80 m H Σ
Σ
(x) (1), oh m)) (Ir & MHSA.
m,kij
(x.))ESxAAm.k)
This completes the proof for Equation 22
Proof of Equation 25 We diedtee in (M- (H- and split the summation into two parts:
kmikk
k.
(V++1 h+1
Viitz)(0
m.
mi
Mimiis
S i1 Σ
Vitta (a
m.k.j
inl
0 a (V
Vi+1)( (o )
m.k.j
To bound the first term, we first notice that
Σ Itm m.k.j
I dil
kmm h-1
Vh+ Vott
(m.k)))a
S H Σ
1
th tmi
< i1]
m.ka
due to the fact that (V Aes
V (2+ (++1 (o
misk ) and -i
Ø 0mm.k = Ilt. > 0] given
suppose that ke' is the round index such that N (x,a) S i and No (xx,a) > i1, and k" is the round index such that N (z, a) = 0 and Ng (z. a) > O. Here, K' and k" are simplified notations for functions of (ar, a, h). and we use the simplified notations when there is no ambiguity and the stated meaning is only valid in the proof of Equation 25
in (c) in Lemma B.3 For every (a, a, h) E S Ax [M),
+1
We have
Σ I/0 < th m.kkj
mmkk < i (1]
k... aa km)kk)) = (x,, a)] S in + nk (2, - n (a)
As n2
(z, a) 2 and nit (a, a) S M due to No (zz, a) < io and Equation 12).
Σ I10 < hh
k.j
< in (x (n ah
k.j. k.j = (x. a)) $ < (M - 1) = 0 (H²
So,
E1er ki
< {1]
k.
(V
kmaks
Viit))(0441 ( (m.kk.))
1=1
S H
Σ
Σ
I[0
m.kks. th
s &|]l((]) (, ,0 kRt (I,
(x.a)ESxAm.. Am.k.
= = 1)).
(28)
24

---

Published as a conference paper at ICLR 2024
To bound the second term, we first notice that V
13). Then we regroup the summations in a different way. For every (m' k', j'), the term (V (1+1)(0141 mn m d')
Vh++ 2 0 due to Equation
appears in the term T(% in in
Of A. (V
) for (Ri, m,,) if 1 (artr (m).k.)
i=
and only if k k' and (#h (itti an
(2% mor M' m m''K'"" K'') Thus, for each (m', K J"),
denote ax) a) (at K' m'.k'' We consider all the later round indices k' = ko < k < 22 <... that satisfy nl "h (ar,a) a) > 0, 8 E N. Here, ky 's are simplified notations for functions of (m',k,J" j",'",,), and we use the simplified notations when there is no ambiguity and the stated meaning is only valid in proof of Equation (25). Then, the coefficient of summation related to (m', j') can be upper bounded by
,ah
J > in NY (2.a)'
in which is the global visiting number for (a, a, h) at (m', k,)'), which means that (m', k') = (1': 2, a), kn (2': a). (t"; a).
First, based on (c) in Lemma B.3 we have that
Σ I (z,a) > inlmaO Na (r,a) S exp(1/H)
I[ (Ir > inlma Mt (r.))
(m,a)'
We know that, N (Ir, + n, No (x, 1' S No (ar, az) and by (d) in Lemma B.2 Dm Of = (1 1/H). Therefore, if we can find C² > such that
8% NN (z.a)
C' 2 max (APEE N (2,a)+5"
where A= (1) E N N (I, 11, < < n, we can have
Σ ( (z, a) > in N (m.o) S C³ exp(2/H).
Next, we prove that, for any (1' E A, if No. (z) i1.
0r
No. (2,a)
N
Noka (2,a)
No* (2.a))+15"
Noh (m,a)
N (2,0)+n,-1
II
(1-aa)-
d= (p.a)=1
< (1 ado) 1-
S (I)HL,
in which do N/. (I,a) a) + that can let C' cxp(1/H). The first inequality holds because axy) is a decreasing function with respect to t. The equality follows from
0: = a; I the definition of 0f. The second inequality holds because a; WFF respect to f. Then we focus on the last inequality. According to the definition of oz, we have
H+1 is decreasing function with
(
- H N
H +1
1-ne
-(1+
H+1
Re-1
(1 add 1-m)
No. (I, a)
If NR. (x, a) > MH(H + 1), according to Equation have
12 we have that n, 5
No (2.a) H(
Then we
(a.0)
(1 11+ H+1
n--1
(
H
-
1+
5 exp(1/H).
N/k (x, a)
Nrk.
(xx, a)
25

---

Published as a conference paper at ICLR 2024
i < NY (z, MH + 1), can prove that
(1+ H+1
n.
1A
H +1
M-1
1 1+
No (2,
No (I,
1
M1-1
H(M - 1)
W
(1/H)
where (a) holds because according to Equation N/ (ar, a) (M HH + 1).
12 we have n2 I M and (b) holds because
Putting the two cases together, we have
Σ (1, > in (a,0) S exxp(1/H)exp(2/11 S exp(3/H).
Then we conclude that
m.k.j
EnTm
Memiked
'1
@ ki
(v++1
Vhe (1h-11
m.k.j
Σ
(vitz Viita) (xht1
S exp
H
m K '
exp
Ph+1-
Combining with Equation
28 we complete the proof for Equation 25
Proof of Equation 26
We split the summation into two parts:
B A.m. M.g
Σ
Σ
B B.m. T(O m.k.j < M
1] + Σ
Bem Timm.dss
&. 2 M].
k.
m.k.j
For every pair (x, a, h). we consider all the rounds indexed as < 1 < K2 < ... satisfying the k. condition n1 n (xx, a) > 0. Suppose that kp is the round index such that "
(I, a) - M -
and N N (x. a) > .M - 1. Here, kgs and are simplified notations for functions of (x. a, h), and we use the simplified notations when there no ambiguity and the stated meaning only valid
in the proof of Equation 26)
To bound the first term, we use the fact that 3.m...s I <O(1)/ H
Then we have
Σ 8.m. I10 < th k.j < M 1 OL1VH3 m,k.j
Σ10
1 < th
m.
<M- 2M-11
m.k
and
Σ I < Kittk M- - 1|5 m.k
Σ
M M-142
n
(x,
a)
n (z, (x.a))
(x,))ESxA
is straightforward that n (z, a) > 1. Additionally, due to Equation
12
we can establish that
By n (I, s M. Therefore
I10 jnn < M 1| $ 25A(M - 1)
m.j.j
and
Σ k.k
B.m.
TIO
< th
mm,kj
< M 1| ((SA(M-1)VFF))
(29)
26

---

Published as a conference paper at ICLR 2024
To establish bounds for the second term, we define some notions first. For every pair (x, a..aa)) h)
8 x A [ consider all the rounds indexed as 0 < l < h S K satisfying k (ar, a) > 0, No (zz, a) 2 M and N a) < M. Here, k,s and g are simplified notations for "
functions of (æ, a, h), and we use the simplified notations when there is no ambiguity and the stated meaning is only valid in proof of Equation (26).
Then we have
E 8 Bemas m.
k.j 2 M] O(1)
Σ (2.0)E8xA*=)
Σ
ko n
(x, a)
H
No. (x)
Firstly, we prove that
(2,0)
Σ
H
(1)
Σ
V HHIL(NE2 (z, + m (z, 1)
N (z) j
(#.))SxAA=L
juml
(x,0)ESXA
=
Σ
(z,a)ESXA
(a)
< O(V H2ÍSA
where (a) holds because of the concavity of f(x) E(maeeS NK+1 (x,a) $//H.
HLL and the fact that
NN.. (m.a)
Then we bound
If we can find some numerical constant C" > 1 such that
v NN (z,a)td
No (x,
c² max G
(a,a,h)e& Ax [H],
Nr. (z. +d
which
B ((s,d) N2; S 8 S g, 3..1dd5 ds
nh
(I, a) 13. then we can have
Σ M.J.j
> M] 0(1
Σ
m (1r, ay
Ry
3
No (z,
(x.4) mmm
(w.a)
H3
50((")
Σ
N (I, +
(2,0)
s=1
="=1
= O(V H2(SA).
(30)
Next, we will prove that we can choose C" 22. We notice that
1/V No (2,
i a) + nx (z, (z,a) -
de In R (x.a)
1/ V No. (I, (z, +
(2,
If M & NÝ. N (z,, a) < io. according to Equation
12 No (x, a) + n R (2.0)
(z(5, a) S M, which indicates that
$ 22.
Nh. (I,
If N (m,a,)))) (I, io. according to Equation
12).
Ke ni
(x. a) &CN (x.
No (z, a) + n (I, -1
VI+õs V2.
N (z,
So, we can choose C"
22
Combining Equation 29 and Equation
30
we obtain Equation 26
27

---

Published as a conference paper at ICLR 2024
D PROOF OF THEOREM 4.2
Proof of Theorem 4.2 This theorem is proved under the synchronization assumption, i.e, n n Vm E [M.. We only need to prove that when & 2 HH + 1)SAM,
[1+
[K/USSA]-
+ ST.
( + 1)M
For each [K]. there exists at least one (z. m) E S [M] x [H] with a TH (x) such that equality in Equation (1I) holds. Thus, there exist at least K different tuples of (x. a, h, m, k) E S x A [H] x [M] x [K] such that equality in Equation 11 holds. Define set K. to have all the different
k's satisfying that there exists E [M] such that the equality in Equation (1I) holds. Then, by
Pigeonhole principle, there must exist a triple (z, a, h) E S AxAx [H] such that [ 2 [K](HA))].
We order the elements of KC 0 < kn < l2... < kn S K, where 9 2 [K/(HS))) We also denote N₂ NNt,+1 (Ir, a), m, the first agent index such that equality in Equation (11 holds, and makk (I, a). Due to the synchronization assumption, we have n2 = nh
72 HM
(31)
When N₂ 2 H(H 1)M we have that
N₂
ny no+1 (2,/(2M)
due to Equation (11 and
2H as' > M(H 1)H.
H(H+I)M
Thus, we have that > sml
H(H+))M
n, 2 H(H + 1)M and
ns CN./(2M) (1 C1(2M)) Σ ng, 2 H(H 1)M.
ns
Therefore,
g
(1+8/(2M) ((M+1)M
H(H + 1)M
(1 (1+8((2M) [K/(HSA)]-
H(H + 1)M.
Combining with Equation 31,. we have
[1++ 2H(H + 1)M
[K/[HS))]-H(H{)
1² + 1)M² ST,
which directly leads to the conclusion.
E THE BERNSTEIN-TYPE ALGORITHM
E. ALGORITHM DESIGN
The Bernstein-type algorithm differs from the Hoeffding-type algorithm Algorithms a ? in that selects the upper confidence bound based on a variance estimator of X,, akin to the approach used in the Bemstein-type algorithm in Jin et al. (2018). This is done to determine probability upper bound of Ei= O.X. In this subsection, first introduce the algorithm design.
28

---

Published as a conference paper at ICLR 2024
To facilitate understanding, introduce additional notations exclusive to Bernstein-yye type algo- rithms, supplementing the already provided notations for the Hoeffding- typpe algorithm.
Ph
m. (x, a) m. (x, a)
Vi++ (*
M[(0 a am (2, a)}.
n
(x,
pn " (x,
No (I, N/ a)
1ith"(x; (x, a) is the sample mean of [ (a))) for all the visits of (æ, a, ft) for the m-th agent during the k-th round and (z, a) corresponds to the mean for all the visits during the k-th round. We emphasize here that we adopt the general notation n=" in the definition of f% m.k We define (a( a, h) denote the sample variance of all the visits before the k-th round, calculated 3. )...e
Here, 1h
using h+1 (2/11
(z..)) Σ
(z V Vi
We(z,a,h)== (1
Vo Vitalanit
1
Σ
(x,
We can find that
We(1, a, h)
(a, (x)
No(o,
an, (2, (x,
(x)
k=1
which means that this quantity can be calculated efficiently in practice in the following way. Define
Wz,(z, Σ ph (z, a) (z. (2, Σ (4 a)nk (2,
(32)
have that
W WI,+I(Z, Win a, h) + u (I,
(33)
W h) W2, a h) + uf + (x, a)m
(34)
and
W WI, (x,
W 12, (x,
(2,,
(35)
This indicates that the central server, by actively maintaining and updating the quantities Wi, and m.,k m.k and W2,k and systematically collecting ni ph 141s,, is able to compute W Next, we define
m.kk
(minn) min {V Hh (W a, + H) +
SHTSA + MSAHG
H3t
Be a, hi) = df
in which c' > O is positive constant. Here, Wi a. (', a, h) which is mentioned in Section With this, the upper confidence bound by(2, a, h) for single visit is determined by
a, = 0, a,
which can be calculated as follows:
by (I, a, h)) = B1 (xx a, h)
2
be () Be(r,a,h) - ar) Br (2,
2a
29

---

Published as a conference paper at ICLR 2024
When there is no ambiguity, adopt the simplified notation by by (1 a. h) and B, 3r a, h). In the Bernstein-type algorithm, we let 8 Bet a, ht) az (1 1, Baa- ) 1 (xc, a, h)) in replace c', indicating that the Bernstein- -type algorithm operates with smaller upper confidence bound.
of ge in Equation 3 and Equation (4) We know that 3, S 3r when
Next, we will delve into certain components of the algorithm in round k. We remark that we dis- cuss our algorithm based on the general situation where there is no necessity for zero latency and synchronization assumptions. In this general scenario, agent m generates nm=h episodes round k.
Coordinated Exploration for Agents. At the beginning of round k. the server decides determin- istic policy n² f H h=1- and then broadcasts along with { (2,, (=)) and {V/ (v) (x)) bn all of the agents. When k . (z, a) 0, Q (z. a) V (z) = H, V(x, a, E S x A [H] and I is an arbitrary deterministic policy.
Once receiving such information, the agents will execute policy T² and start collecting trajectories.
Event-Triggee Triggered Termination of Exploration. During exploration, every agent m will monitor m.k/
" (I. a). i.e., the total number of visits for each (ar, a, h) triple within the current round, For any agent m, at the end of each episode, it sequentially conducts two procedures. First, if any (xr, a, h) has been visited by max { [L, Ar N (z, a)]} times by agent m, will abort its own exploration and send an abortion signal to the server and other clients. Second, it checks whether it has received an abortion signal. If so, will abort its exploration. We remark that Equation ( still holds, and for any le E [K], there exists a tuple (I, a, h) such that the equality is met.
Local Updating of the Estimated Expected Return. Each agent updates the local esti- mate of the expected return m.k (2, a) at the end of round k. Next, each agent m sends (ra(a, (T(a,, ([()))) -. (n% (ar, = (a))),,n (UNth (2x, (x)))) and (uh, (u)ti((a (x,,,))()))) (x))) the cen- Ja...)))...n (m
tral server for aggregation.
Server-side Information Aggregation. After receiving the information sent by the agents, for each (x, a, h) tuple visited by the agents, the server first calculates W W (z, h). W2 & 1 (xr, a, h) and
Wa+1 (zz, a, h) based on Equation (32. Equation (33). Equation (34) and Equation (35) for each pair
(ar, h) with a x (z). Then it sets t
N (z. a), t N (æ. a). Gogg 1-a (th +1, t*)
and B = 3e (Ix a, h) a (th-1 + th 8 (x. a, h), and updates the global estimate of the value functions according to one of the following two cases.
Case 1: N (z, a) < in. Due to Equation 2). this case implies that each client can visit each (x, a) pair step h at most once. Then, denote mi m2.... < mys - S M as the agent indices with ni (zx a) > O. The server then updates the global estimate of action values follows:
m.k
2 a) (1- aaggaagg))00 (2) ang
Σ
0% - u
me (x, a) + B/2. (36)
. Case 2: N/. (xr, a) 2 ig. In this case, the central server calculates t (x, a) as and updates the Q-estimate as
) (2,a) (1 aogg Q (z. a) + aagg (ra(æ, a) + v (z, a)) + 3/2.
(37)
After finishing updating the estimated Q function, the central server updates the estimated value function and the policy based on Equations (5) and (6) The algorithm then proceeds round l + 1.
Algorithms 3 and formally present the Bernstein-type design. Inputs Ki and To in Algorithms 3 are termination conditions, where K, limits the total number of rounds and To limits the total number of samples generated by all the agents before the last round.
We provide some remarks. First, the coordinated exploration for agents is designed based on the general situation where n. might be different across different agents, and clients share μ m in addition to the information shared during the coordinated exploration in the Hoeffding-type Algo- rithm Second, the information aggregation at the central server differs from that the Hoeffding- type Algorithm in terms of specifying 3 to set the upper confidence bound and in maintaining W1, Wi,k; W2, and Wt-
30

---

Published as a conference paper at ICLR 2024
Algorithm 3 FedQ-BBrnsstile (Central Server)
Input: To, Ko N+ 2: Initialization: & = 1, (r, a) = Wia(a,a, h) = W2,2 (z, a, h) 0,
=
H, Ma,,a, h) E S x x []] and x² = (T S + A he(H) is an arbitrary deterministic policy.
3: while H E Mn < To & S Ko do
4: Broadcast x², (NZ, (ar, (x)) a.h and (v)( (x))
to all clients.
5: Wait until receiving an abortion signal and send the signal to all agents.
6: Receive {rı(z, (x))) 22 (nmm (z, T.. (x)))a,
{o
and
(uh (u,, (x))) from clients.
7: Calculate N (z, a). n. (2, a), of (z. a), v(a, h) ESX [M] with a (x))
8: Calculate Wa(2, a, h), Wx+1 a, h). W1, (I. a.h), W2.+1 a.a.hh)... h). v(r, h)
[H]
with (x) based on Equation (32). Equation (33). Equation 34 and Equation (35
9:
for (x, a, h) S x AA [ do
if a # (z)()) or (x, = 0 then
11:
Qh (I, a) t (2,
12:
else if ( a) < in then
13:
Update Q (x, a) according to Equation (36).
else
15:
Update Of+t+ 1 (xx, a) according to Equation 37
end if
17:
end for
Update Vi V and π h according to Equation 5 and Equation (6).
18:
19:
k 4 k: +
20:
end while
Algorithm 4 FedQ-Bernstein (Agent in round k)
1: (x, a) = o/4 (x, a) = (2 a) = 1, a) = 0, (ar,a, E x A (H].
2: Receive n² {N (x, (=)))=, and (V,())) from the central server.
3: while no abortion signal from the central server do
4: while ni (Ih, an) max ( L (Ih,, an)1] V(z,a,)) E x Ax [11] do
(Z,,,,
5: Collect new trajectory ((TA, an, rh)) with as (an)
6: n% (In, an) + ni (zh: an) + 1, wi " an) + 1 an) (
po (Ir,, an) < pn (In, un) ( (x)+1)] and (2 an) rhy vh E [M].
7: end while
8: Send an abortion signal the central server.
9: end while
n m.k
(x,a)
nh ni (a, a), u (2, a) < (2, (x. and p makk " (x),))
Pk (x, (0////(aa (z. a), v(z, h) S x [H] with a = =f(x).
11: Send {rx (z, T (2))) in
m.k (x, n (x)))a, (uphi(a,
(x)) and (o (x, (x, [x(x))aa
to the central server.
E.2 PROOF OF THEOREM 5.1
In this subsection, provide proof for Theorem 5.1 which provides the regret of Algorithms and
E.2.1 BOUNDS ON Q - Qi
We first try to provide Lemma that has stronger results than Lemma
C.I
Lemma E.1. Using Algorithms and there exists a positive constant d' > such that, for any
p E (0, 1), the following relationship holds simultaneously for all (x, h. K*) Sx [H] [K]
31

---

Published as a conference paper at ICLR 2024
with probability at least 1 p.
0 0 O (x, a) - (2,, s H
H
(ii h+1 (=+1) ax, Σ (V
(38)
i=1
in which 1 NEK (I,
The remaining content of Appendix E.2.1 is dedicated to proving this Lemma. First, we can easily find that Lemma C.2 still holds with by 3, replaced by be, 3, and Lemma C.3 still holds. Next, due Equation (16) and Equation (15) with b, 3. replaced, we can easily obtain a similar one-sided result summarized in the following Lemma.
Lemma E.2. Using the Bernstein-type algorithm, there exists positive constant do > such that, for any p E 10.1), the following relationship holds simaltaneousty for all (x, a, h, K*) S x A X H x [K] with probability at least 1 1-P) p.
mi Q (x, (2) 02H Σ 0i V=+ CVVH3/
(39)
in which t = NKK (I,
Proof. This relationship can be directly obtained from Equation (66) and Equation 15 with bi, 3 replaced.
With this, we can introduce the following technical Lemma.
Lemma E.3. Suppose that Equation (39) holds. For any given K' E N, denote Em,
EK 1 mn and vec( (ewwk) with E [M], [K'].] E [n be non-negative vector. Then there exists a numerical constant &j > such that, for all K') E {H) x [K].
K' Σ mikj
(V V% (2 k2)))
m.k.
S d
(S M H V /SA/wwla bo// Ho HASA(M (0((M-1))10 1)]lwo/oo))
(40)
Proof. We denote
V/ (1th (mmk..)) Vi (ai
Oh (19)
m.s m.k.s)
ve (1 kmm) and Q% mikis mikks a
Noticing that
oh
maxacA Qi Ih kmsses) S have that
Vi Uh
m.kk.))
letting I = K' and (2,a) = (0h miki ap m..k.) we
F.m h
<
00
H
Ro k.y h41
(m.. dov Ha//lm
Taking the summation with regard to le from 1 to K' and noticing that 0o po have
k.jjk. >
0). we
K'
m.
Wmkg k.j. <
Wmay
k. = 0] + Σ
Winke
6 miiis V/41
m.k.
m.kuj
m.ke
K'
H3, m mm,
Wink
m.k.
Next, we find upper bounds with regard the three terms.
32

---

Published as a conference paper at ICLR 2024
Step 1: finding an upper bound for H Σ
m by w Wmkj (h
K'
m.. 0). Noticing that Winks I 1|o/oo.
using the same way as Proof of Equation (44 in Appendix C.4
we can find that
H Σ
Winky 1
Immkk 0J S MHSA||wlle
1mike Ge Step 2: finding an upper bound for km.k. Wmkjj 2
V (m) Similar to Proof of his h+1
Equation
25
C.4 mi
in Appendix
with i (M - 1) = 1), we still split it into two parts as
follows:
Kf
K'
Wmnj
Σ
8 ans
V. (m.kk))
1+11
Σ
Wmkj Iitm
$ siil
V
ka h+1
(m,kJ)
m.kk.
m.j.
K
Σ
Iitm
Σ
8
Winky
h+1
m,k
For the first part, applying Wikj we can find that
I ||wloo, using the same way as Proof of Equation 25 in Ap-
pendix C.4
K'
( I <O(HSA(M -])[[w]]oo)
Σ
Wink I[tm.
S 11
c
h+1
k.k
For the second part, we regroup the summations in a different way. For every (m', K'j'", the term
T'm's Tym(K'' K'' appears in the term Winkl Tltm. in E h+1
0s
mmmtt 1. (miiki)ihh for (k, if and
h+1
only if K' 2 > V and (mm..kd aa mink (w) m K'
m S'.... So, for each (m', K' j'),
denote (x, a) (2% m' s' m K W.).. We consider all the later round indices k' ko < k1 < h2 ,a,
kg S K' that satisfy n, ny (zx a) 0, E N. Here, k,s and g are simplified notations for functions of (m', ".j", h). and we use the simplified notations when there is no ambiguity and the stated meaning only valid in proof of step 2. So, the summation of coefficients related to (m' K',')) equals to
NK (2.0)+no
Σ
T[N (I, 11)0% NY (x,))
Wm
W (inkjytaa
(250)+1
in which / is the global visiting number for (ar, a, h) at (m' W. J'),,, which means that (m', ,'j') 2,,)),
ma(i'; 2, a), kn (t';
a). This means that
Σ
Wmkz Dimmk d1]
Σ Ø
V. (m.kk.)7k
h+1
Tmeke
Fmm M h+1
Denote i vec( (0))))))) }), we have that
K'
1 Ans
K'
|
1
Umky [[c
i1
Wmnk
g
m. h.s S ||00
%
m.kkj
m.J
1
due to (c) in Lemmal
B.3
We can also find that
n.llw]|s<I[[/ (x, > &100
x100%
I cxp(3/H)|lwll]
Ny (2,a)
where the proof of the last inequality is the same the Proof of Equation 25 parts, we have that
Combining the two
K²
K'
Σ
m.s.
Σ
Kk
K 5 +0 +HHHSAAM -1)[(oo(ee))
Winkj
h+t1
Wmikiy hti
33

---

Published as a conference paper at ICLR 2024
Step 3: finding an upper bound for Lm,ks Wmkzsl (v
H
We split it into two parts as fol-
lows.
K' Σ
(V
H
K'
Wmky I10 < mma S - -1/2 (1
H3,
Winks52
mm.k
Σ
mm.
m.kid
K'
(1
H km, ch
Wmky
2 M1Q
m,kj
For the first part, applying that Winkj have that
S
||||
oo similar to Proof of Equation 26 in Appendix C.4
K'
H3r pmike
pm. < M 1111 W0 < l/2
S (11
For the second part, we denote (2, h.) = =m== also introduce the following notation. For every pair (x, S A [H] consider all the kr rounds indexed as 0 < k1 < k2 < < kn < K satisfying n (z, a) > 0, N (z, a) 2 M and No N/ (I. a) < M. Here, k,s and g are simplified notations for functions of (æ, a, h), and we use the simplified notations when there is no ambiguity and the stated meaning is only valid in proof of step 3. Then we have
2j=1 Winky [[ o km) = (r,a)). We
n m.k
m.k.j
K' Σ m.k.
H3r
H3t
Wi Ms (1
2(1)
Σ
Σ
(x, (2,
R,
(x,
(=.a)ESxA==)
We also define that
w (i, a, h) = why ar, h)/nk & (x, (r, a. E ( (2, (2, + n (z, a) 11.
which indicates that
w' w',,,,,,h) s 1
Similar to Proof of Equation 26 we have that
1 N (2,
V
max (i
V No (2, +d
in which B = ((s,d) E N 15 1 < d < n/ R
(x. 1}. So have
Ny - (a.0)-
H3r
Σ Σ w (I, (1)
0(1)
Σ
((i,
Nok. (c.
(x.))ExxA=s #=1
(a.0)ESA
(=N))
with
Nf (x,a)-1
Σ
Σ
w'1,, s ||l|
(x,A)ESXA N
NNfo iNfut1
( (x,a)-1
Denote u ||
w a, a,F,,,,,//1l w//l which indicates that
i= (x,a)
No (x.a)-1
w" (x, a. h.hh) h)
Σ
w (1, a, h) ||
i= N (2)a)
34

---

Published as a conference paper at ICLR 2024
so that
Σ az S 1wlll + SA/Wwloo
(x.0)ESXA
Then by letting the mass related to {w'(i, 2, a, h) concentrate at large values for { (V 1//// much as possible, we have
as
N (x,a)-1
N
Σ
a'(i, Ha/i 1101
N (a.a)
(ara)
=0 H=' (z, ho)hl/lllss
By the concavity of f(x) VH3r. have
(
H
Wmkyyllt [[th 2 M|Q
E
(VVHeee" H/H (2, a, (e),illlllss
m.k.j
(x,0)ESXA
(v WHSSAu(|wlll SA| =>
(VISSAd|w/llll + SAllwlloo v 1131)
To conclude, for step 3, we have that
K'
H3,
So 5 HHSAA S + MSA/|w/l Hag
Wink
(V
m,kj
Combining the results for the three different steps, we have
Σ m.
Wink k.j.k.J
mmk F.m.k.. h+1
+ O +
m.k.j
+ +MS H3 H 1)]
with ||ll|| S exp(3/H1]l and || || So, by recursions with regard h, h + 1.... H. we can get the result.
Next, we will establish relationships between Wa(2,, a, h) and [V+ (z, in which [VaVital (x, a) a variance operator define below. We also need these definitions for any (I,a, h, K') E Ax [M] [K 1] with & N (x,a).
|P 1 (x, a) = EVVi+ (I an) (I,, a)).
WaVael (z, a) (() V (z') [PAVitl] (z, (s)a))==
Here, P1 depends on (z, a, h) and we will use the simplified notation when there is no ambiguity.
i Σ
Vitta (h411
[Pn VPaVital (ct, (c) = P:
(a h+11 (ommAtiitiiaa)) ]² Ps
Σ
Vitti
( (1ttaiia))))))))
2h411
Σ
Vhttn
i=1
72
Wx. a, h)
1 Σ
(t (om.eaaatt shh11
Σ vhall'sza)) (1fmAAsaaattszza)))
(5/41
Pa-
Here, Pz, Ps, Pa depend (a, a, h, k) and the simplified notations when there is ambi- guity. The following Lemmas establish the closeness of these quantities to illustrate the closeness between Wx
Wxe (2. a, h) and [Va Vital (z
35

---

Published as a conference paper at ICLR 2024
Lemma E.A. For any p (0, with probability at least p, the following holds simultaneousty for all (s,a, K') E S A x
H [K with N/K (x,a).
PP 0 11 112 v1f(
Proof. We have that {VVTs (1(mn)-))aa(i..aa)))
(Th+1
1 i (I, a) Pt
20
a martingale dif-
1=1
ference bounded by O(H2), and the random variable S T1 + C). By Azuma-Hocfiding Inequality, for any given (x, a, h) S x [M] and given t' N.,, for any p (0, 1), with probability 1 -p
(1(ttaa)aattsaa)))) (Iviss (iri((((ff (*/+1
Ph Vitta (x, a)) P.) 0o H²
log 2
By considering all the possible combinations (I. a, h t') E AxAx x [To(1 C) H + M with union bound and the realization of t = t', we can claim the conclusion.
Lemma E.5. For any p E (0, 1) with least 1 - p probability, the following holds simultaneously for all (z, a. K)) E S x Ax [ x K + 1] with t = N (æ, a):
P2 Pal - H2 V1ft)
Proof. We can find that
1
- 11
7 Vitt
7
2 2/+1
( - PA Vitza (z, at
Knowing that { {Vitt
(1
[Pn (c,, (1, 80 is a martingale difference
(++1
bounded by O(H), using the same procedure as proof for Lemma E.4 we can claim the result. O
For PP3 - Pal, similar to the proof of Lemma C.3 in Jin et al. 2018), we have
PP3 Pal 5O
H
Vh+1
(iar,a)
(m.k..)) (. -h
Vitta
(km (Th+1
We mark an event Equation
(41 here, which means that the difference is always non-negative.
Event(K')
vik
(um² (m""""" - Vi++a (o/+t1 (om))(s)))
(Tht1
Vit (omaat"")) - Vhtz (anti (orltss)))) ((a, M
=
A+1
1h++1
i=1
(41)
We do not need a new statistical lemma to prove that it holds with high probability. It will be shown hold automatically based on some other statistical events that hold with high probability later. Under this event, we need to find an upper bound for
Σ
v (i:r,a)
(1 (m..k. ((im--ahaa(tseeee)
Vii+i (Th41
h+1
Th+l
Under the event of Equation (ar, a)), we have that
(39 based on Lemma
E.3 letting Wonjj
miki miik))
1
Ni (H:m.))
(m.kii)) (12..))
Vi+i (#/+1
(m.hii)
((tn)))) (Koma))
i
0
MSA
H
V
SA
H (ASA(M-1))
36

---

2 p Published as a conference paper at ICLR 2024
which indicates that, under the intersections of the events of Equation (39. and N==1 Event(k), for any (z, a2 S x A [H], we have
K"
MSA
H VSAHT (M 11SAH
PP3 - Pa 00
Vt
t
To conclude about the relationship between Wa(a, a. h) and [V (z, a), we have that, under the interaction of the events of Equation 39 k= Event(k), Lemma E.4 and Lemma B.5 we have Va, a. h, k) E x Ax H x [K']
Wa(r, - [VAV (r)a))
MSA
SAHT
(M 1)SAH$
0
H
(42)
Vi
With this relationship, we can provide the new concentration results. Similar to the proof Lemma C,3 for a given ar,a,h) E S x A [H], we decompose the summation Ei= 0i as follows.
Σ 0X1 = 0X + 1=1
( 0
i=1
Equation 119 has already provided upper bound for all (a, h K') E A [H] x [K] for the second summation. Next, we focus on Σí= X By Azuma-Bernseein Inequality, for any
fixed E N and fixed (x, a, h) E x [H], for any E (0, 1), with probability at least - p. have that
Σ x 5o (O [V (z,a) log
2 1 22 log t'
After considering the union bound with regard (z, h) 8 A [M]] and t' To/ H, we can claim the following conclusion: for any E 1), with probability at least 1 - the following relationship holds simultaneously for all ax, K') e SSxA [H] [K].
x so (V (z. + ( :..==NKee N
(V
(43)
The intersection of events of Equation (43) and Equation 19 indicates that the following relation-
ship holds simultancously for all (Ir a, K') S x И [K] with NN a):
(Ee,a, Em.a, Vi (In+1) 0o (V
<
[VaVin]] (2, + -1? + VHuft): (44)
Combining with the event of Equation (42) for K' replaced by K' 1, we have that
0 (Beja.hi - Ex.a,)) Vi (2a-1)
(
MSA 00 1H (Kr41(e,a,1))+
VSAH
(M - 1)SAHS
HT
Vt
+1112 + (Holl).
37

---

Published as a conference paper at ICLR 2024
Due to v HTSA < H +
SA
we have that
0 (1
MSA W WK
VSAHT.
+ (M (M- 1M)-SAAAH
1
t
Vt
(V="
00
H ( + MSA
V WHIL+ H SAH
(M 1)SAH
t
t
t
0o
(V (WicHsleaa))++ + MSA
VH 11 + SAH
(M -1)SAH
t
Noticing that
MSA
HHL+ (M 1)SAH
O ( t
MSA H8.)
t
we have
02 (Bz,ahhi - Bex,ah) (xn+1) (m. (2(
Hu (Wxxi1s,,)) H) +
H + VMSAH
0
(45)
which indicates that
Σ 0%
(Ez,o,h,t Ex,, ((r1((t))))) a3)
when combining with Equation
39 and df is large enough.
Finally, we are ready to provide proof for Lemma E.1 We let to be large enough and Will provide discussion under the intersections of events for Equation (19), Equation (39), Lemma E.4 Lemma E.5 and Equation (43). We know that these events hold simultaneously with probability
cpP
some Cp O. Next, we will prove Equation (38) by induction. It obviously holds that for all (x, a, h) E S x A x [H] when K' 1. We suppose that it holds for every K' < K/. When
K' = K₁ + 1, LHS of Equation (38 indicates that Ok=1 KG+1 Event(k) holds. By the discussion
above, this indicates that Equation 45 holds for Kg 1, by recursions on H, H 1..... 1 (similar
to the proof of Lemma 4.3 in lin et al. (2018)) we can prove that Equation
38 holds for all
(a,, a, h) E S A x [H] for Kg 1. This finishes the induction. After replace p with p/cp. finish the proof.
E.2.2 REMAINING PARTS FOR PROVING THEOREM 5.1
Next, we begin to discuss the overall complexity. Similar to Lemma C.5 in Jin et al. (2018). we will provide the following Lemma.
Lemma E.6. For any E (0, 1), with probubility least 1 - P.
Σ
Vn m.j.j ,ap
m.). < O(H + H²)).
m.J.J.h
Proof. We assign an order for all the episodes based on the "round first, episode second, agent third" rule and suppose m(i), (()). recovers the agent index, round index and within round episode index for the i-th episode. Denote R; ΣH V, (= (m..k.)))))) a% (m,,)))i) and F; be the -ffieed generated by the information before the i-th episode. Similar to the proof of Lemma C.5
(=
in Jin al. (2018), we have
E F < H?
0 R H3
38

---

Published as a conference paper at ICLR 2024
Var Fa S H
So, by Azuma-Hoefiding Inequality based on Σi=1 1 R3 with regard the filtration (Fi) and union bound for - To(1 + C1/H H + M, we conclude that
T/H
Σ m.k.j.h
(oh (mmi. mikk VnVitt
Σ t=
R. SHSOHHT HH)).
We also provide a Lemma that focuses on the concentration of ch. Lemma E.7. For any p E (0, 1), with probability least p. the following relationships holds simultaneously:
K Σ
C₂
S O(HVTI)) V (H),
(46)
Sh+1
A=1
h=nh'
Sh+1
<O(HVTI).
(47)
in which C₁. exp(3(h 1)/H).
Proof.
We first focus the first event. Denote
((m,k,j,h)
Ca
P) h+1 Vi+i
(x) mikk
.h mikk)) and
simplified
notation
Σ k= EM Ej=1 DM The quantity we focus on can be rewritten as
Σ V(m, kij,
M.A.A.A.N
with [V(m, h.) S O(H) as Cn & exp(3). Let Vi be the i-th term in the summation that contains î(H h')/H H terms, in which the order follows a "round first, episode second, step third, agent fourth" rule. Then the sequence (V(1) is martingale difference. By Azuma-Hoeffding Inequality, for any p E (0, 1) and E N+, with probability at least - p.
Σ V
< 00
0 (HVi)
Then by applying a union bound with regard to E H 1] and all possible t which is divisible by И - h and knowing that Г(Н - h')/H < Tb(1 + Ō* + HM due to (c) in Lemma B.1 we can claim that, for any p E (0, 1), with probability at least p. the following relationship holds simultaneously:
K
H
7(H-N/H
Σ
Cr
Σ
ck
Σ
v
s <O(H/T)) vh' e [H].
Sh+1
=
h=
The second event can be analyzed similarly for the same conclusion. By combining these two events and re-scaling p. we can claim the result.
Next, try find the upper bound for the regret. We pick c' to be large enough and discuss based on the intersection events of Equation (19), Equation (39). Lemma E.4] Lemma Equa- tion (43), Lemma E.7 Lemma E.I and Lemma E.6 They hold simultaneously with probability
least 6p where e > 0 is a numerical constant and indicates Equation (42) Similar to the
discussions in Proof Theorem we can claim that for vh E (H),
K
S 8 < HHASA++ HSA(M 1) MH HASAMM -1).
(48)
39

---

Published as a conference paper at ICLR 2024
due to Be(x, a. h) = O( HDfft). In addition, due to the relationship
Σ o exp(3/11
Sh+1 + O(1)
Σ
Pemikis (2 (omiites
m.J. hh)
k,m.j
+MMHSA + SAMM
which can be obtained similar to the situation in Appendix
C.3 for Proof of Theorem
denoting
Σ Ekmmjhh mi Enen have
+PT)))+++
Σ k.m.j.h
dem (Itii m. h) (49)
On
1=
We will bound the last term by splitting it into two parts.
Σ
Ben (1% R.j. m....
h1)
= Σ
Pem (1t
mid m.k. b))l S M -1]
k.m.j.h
k.m.j.h
Σ
B Beminis (10 (somiks ahh aniks, h)]l( M).
k.mjj.
For the first part, knowing that Bem.e. (2%
k.j. m.j.
ah
hh) - O(VH3)) using the similar technique
Proof of Equation (26), we have that
Σ
B B. his (1% miid
m.kk
< M - 1] s ONSAM
R.m.
For the second part, we have that
Σ Bemoles (3% m. m.j.
h)] 2 M
ohh
k.m.th
Σ
Hi (WK+1(x)) (a)tikk aa
m.k.. h) + H) +
SH'S + VSSH mm.
j.jj.
m. M]. Il0
Later on, we use another simplified notation same technique of finding C" in Equation (26). we can find that
Σ Ekmjjhh = Ek.m.jhh Mitiiies 2 M). Using the
NK+1 (2.a)-1
Σ
1/tm (0()
E
Σ
1/1 HSA
(50)
k.m.j...M
(xx0,)))SxA((M)
S=M
and
Σ
1/v 1/Vin.hi mm.
<0(1)
Σ
Σ
1/15 V HSAT.
(51)
(x.a.))SSxA(II))
L=M
So, we have
H SA + 6
Σ
< &HS (VHTSA+ VMSAH)).
5 mg
km
We also have
Σ
V gmi (Wa
H
miki m.k. h) + H)
R.m.j.hs.
<0(1)
Σ
m.k. n) m)
Σ
H
e ko
m.K.J.MMM.
M.R.s.
O(L)V <OLLV HHSAT
Σ
WK+1 m.
an .)),
m.ked
m.K.J.M...
40

---

Published as a conference paper at ICLR 2024
where the first inequality follows from Cauchy's inequality and the second inequality is due to Equation (50).
To conclude, we have
Σ
a mm. 0n mikk .h)
R k.m.j.hh
=0 HSAMM -INN-IIIIIHHHHHHSSS A AMS
+V
Σ Wa+t aa
mikk m.k. h)
(52)
m.R.j.b.M
Next, we to find an upper bound for
Wk+1 W ah
m.J. m.k. h).
R.JMM
We know that
Wa(z,a,h) vn
(I, + [Vaa
( (I,a)
Wa(a,a,
h+1
V.Vh (x, - Vv (z)
By Lemma E.6
Vo [V m.k. m.k.j 5o an
I 20(VIT++ (11(+113)
m.K.J.M:M
By Equation
42
denoting ex
pm.k. = Noh (2 m.k.
oh k.s.s).
Vv Viti (1 mo an
m.k.j li)
0o
MSA Tmn
VHL+
VSAHT, (M - 11SAHH pm,
As th
km,
2 th
m.j.k
we have that
Σ
[Va Vitaal
(0t
(om.kk ,ah
m.kk)) We+1 (3
m.d.d m.k.d
a h)
MSA
VSAHT, (M - 1)SAH'
50
VH++
k. h
m.j.j k.jk
M.
AH HASAV (M (M 11
where the last inequality is due to Equation 50) and Equation (TT) We also have
Σ
Wititall m.k.k. a m..k vV, V
(xi)
m. m.ki an
[VAVitta]
(z (.m.k aa k. Vva V ma a k.s.
41

---

Published as a conference paper at ICLR 2024
Next, we will show that, for any (z, h) 8 A [H),
VVaee (z, a) - Va (x - (H() (PP (z,
[PAVatt] (o, a))
Suppose that u, random variables such that follows the distribution of V (2++1) under when (2), an) = (I, a), and follows the distribution of V (I1+1) under x when (Th, on) = (xr a) and u 2 v. The third requirement is reasonable because the distribution of Jn+1 only depends on (z, a) and V (31+4) V (2
We have that u, v v H. So,
[Va (x,
Vn ax)
Var(u) Var(v)]
S [E(x²) - B(v=)(()))))))) + (Bu)² (Eu))²
S [[u v) v) + (Ev - Eu) (Ev
(Ev + Ea)
((H) v)] Bluu vI)
O(H)E(u-u) v).
This proves the conclusion. Using the conclusion, we can find that
Σ Vitiit
(x%
m.kk
On
Vv Vitti (ariieed On km.k..))
m.kijh
s {O(H) E
(I
(2tt , am.kkss - Pn tot1
(2
Oh km.k.)))
m.k.khh
H K
HH)
(8h+1 sh+1 + -hi+1)
K
OH
(8h+1 + ch+z),
A=1k=1
in which the last inequality is due to di based on Equation 38). By Equation (48) and Lemma we have
H K
O
+h
66 h4
HSM(M-
So, have
Σ
m.jk m.j. h) Wx+1 ,ak
m.R.j.M:M
s 00 50 + H SO HH V H -
-1)
= + 5 + + (M)-
where the last relationship is due to
VHSTAA
and
M A 2 MH - H -100M--11HH,..
1)
42

---

Published as a conference paper at ICLR 2024
Inserting it into Equation 52 have
Σ
3 go (x
m.j.j. m.kd
lt) ah
k.m.jhh
=0 - -O C A
+V + 2
Σ
We41 oh aan.ki h))
m.K.i.MMMM
-O -ITIM-1IVVII H3 HJ -H + P CS 13 H
53MH665533377 + 22 A2T05,25 A3 1)
Due
AM 5MH
AM - 1)2 < S S
and
H 52 < H A TSAH32 & 4 VTSAH&?
we have
Bemiiss
m.j m,k.j h) Oh
k.m
- +VIPSATI))
SO
Inserting into Equation
49), we have
K
Regret T) s
ot
k=
= M SA H -) 1) HSAM 13
+ H + + V
Finally, for the probability of the intersection of all the events, if we use p/c, to replace p, we complete the proof.
F NUMERICAL EXPERIMENTS
In this section, we conduct experiments synthetic environment validate the theoretical per- formances of UCB-H and UCB-B (Jin et al. 2018), respectively.
Red@-Beinsttein, and compare with their single-user counterparts
Synthetic Environment. We generate synthetic environment to evaluate the proposed algorithms. We set the number of states S be 3, the number of actions for each state be 2, and the episode length H to be 5. The reward (s, a) for each state-action pair and each step is generated independently and uniformly at random from [0, 1]. We also generate the transition kernel Pa a) from an S-dimensional simplex independently and uniformly at random for each state-action pair and each step. Such procedure guarantees that the synthetic environment is a proper tabular MDP.
Under the given MDP, we set M = 10 and T/H 3 x 10a for FedQ-Hoeffding FedQ Beinsteinn and T/H H = 3 10 . = 1 for UCB-H and UCB-B. Thus, the total number of episodes is 3 x 10 for all four algorithms. We choose c = 1 = for all algorithms. For each episode, we randomly choose the initial state uniformly from S states. We collect 10 sample paths under all algorithms under the same MDP environment, and plot Regret(T)) MM versus MT H in Figure The
43

---

Published as a conference paper at ICLR 2024
12
UCB-H
UCB-B
10
FedO-Hoeffding
Bein-eennttein
Regret(TT) MT
2-
0
50000
100000
150000
200000 250000 300000
Total number of episodes MT/H
Figure I: Regret comparison.
solid line represents the median of the 10 sample paths, while the shaded area shows the 10th and 90th percentiles. As we can see, both single-agent counterpart, indicating that FedQ-Hoeffding achieves linear speedup with respect number of clients M, as predicted by Theorem 4. and Theorem 5.1 Besides, as time progresses, RedQ-Beinstein achieves lower regret than Foeff-ig,,, which is consistent with the theoretical results as well.
and FedQ- -eeintennt stay very close to their
We also track the number communication rounds throughout the learning process under FedQ- Hoeffding and BedQ--Bernstenn and plot the median profiles well the 10th and 90th percentiles in Figure 2 Both curves exhibit sublinear growth, corroborating the theoretical result in Theo- rem 4.2 Besides, the total number of communication rounds under FedQ-Bernstein becomes lower than that under FedQ-Hoeffding as T becomes sufficiently large. This is because after the more active early-stage exploration of FedQ-Bernstein, it reaches more stable policy, under which the synchronization triggered by (z, a, fils that are less likely to be visited under the optimal policy rarely happens.
44

---

Published as a conference paper at ICLR 2024
1750
1500
Rounds of Communications
1250
1000
750
500
250
FedQ FedQ-Hoeffding
Bernstennt
0
5000
10000
15000
20000
25000
30000
T/H
Figure 2: Total number of communication rounds as a function of T/H.
45


Reviews:
[{"review_id": "acXJaMjC5F", "reviewer": "Reviewer_tdCn", "summary": "The algorithm proposes a federated-style Q-learning for tabular MDPs and shows the algorithm achieves linear-speedup in terms of regret, only requiring $\\log(T)$ communication rounds. Two types of uncertainty bonuses, Hoeffding and Berstein, are considered.", "questions": "1. It is a bit surprising that the number of communication rounds is linear in $M$. Can the authors intuitively explain why this must be the case, or if this term could be removed by more involved technical analysis?\n2. Can the authors provide either some lower bound or some additional justification for the overhead terms? \n3. For theorem 4.1, why can we ignore the overhead terms that are on the order of $O(HSAM\\sqrt{H^3\\iota} + H^4SAM)$ in the general FL setting?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The paper's theoretical analysis is comprehensive, comprising of both Hoeffding-style and Berstein-style bonuses.\n- The paper does not analyze the UCB-style algorithms typically considered in distributed/federated RL/bandit, and instead focuses on the harder to analyze Q-learning style algorithms.", "weaknesses": "1. The paper slightly over-claims its results. The regret speedup is nearly linear, but not exactly linear, due to the overhead terms that are linear in $M$, the number of machines, that appears in both Thm 4.1 and 5.1. Immediately after Thm 4.1, the paper also states that the algorithm enjoys a linear speedup in terms of $M$ in the general FL setting, despite the presence of the overhead terms. \n2. While the typical martingale-style concentration analysis in the single agent RL setting cannot be directly applied, bounding each local term's \"drift\" from some \"averaged parameter update path\" is a commonly used technique in federated learning. \n3. Compared with contemporary or prior works on federated RL, the paper focuses on a more \"vanilla\" setting, where updates are allowed to be adversarial or asynchronous, the setting considered in this paper is a fairly simplified, bare bones version of federated RL.\n\nMinor Comments\n1. The term $\\beta$ in eq (3) and (4) should be (at least) indexed to reflect the fact that it changes over time. Preferably, it should also indicate that the term changes with $(x, a, h)$. Otherwise, as of now, it appears that a constant is added to the Q-function estimate at every single round and is misleading.\n2. It might be useful to rename paragraph \"New Weight Assignment Approach\" on page 7 to \"Equal Weight Assignment Approach\", or something similar. Currently, the phrase \"equal weight assignment\" is claimed to be a major contribution, but from the manuscript it is not immediately obvious what this procedure means mathematically.\n3. Please see the questions below on the tightness of the technical results.\n4. Due to the overall similarity between RL and bandits, some literature survey on federated/distributed bandit would be a welcomed addition to Appendix A.", "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": "uEBesOygZC", "reviewer": "Reviewer_62fC", "summary": "The paper studies federated reinforcement learning for the tabular episodic Markov Decision Process (MDP). In the model, there are $M$ agents that play in a given tabular episodic MDP and aim to minimize total regret. More formally, a tabular episodic MDP consists of $J$ episodes, where in each episode, the agents are given an adversarial picked initial state and everyone will keep picking actions till an absorbing state is reached. Each time an agent picks an action, it receives a reward that can help it update the strategy. An agent's regret for one episode is defined to be the difference between the rewards obtained by the optimal strategy and its strategy, and the goal is to minimize the sum of regrets for each agent in each episode. \n\nThe authors first propose a federated Q-Learning algorithm and show that with a communication cost of $O(M^2H^4S^2A\\log(T/M))$, the algorithm obtains a regret of $\\tilde{O}(\\sqrt{H^4SAMT})$, where $H$ is the number of steps per episode, $T$ is the total number of steps, $S$ is the number of states in MDP, $A$ is the number of actions and $M$ is the number of agents. Further, using a higher upper confidence bound, the regret can be improved to $\\tilde{O}(\\sqrt{H^3SAMT})$ under the same communication cost.", "questions": "(1) Are there any simple experimental figures for the proposed algorithms?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Federated reinforcement learning is a very interesting topic and the paper makes theoretical contributions in this direction. They prove that there exists a federated and model-free algorithm that achieves linear regret speedup (compared with the single-agent setting) with a relatively low communication cost.\n\n- The paper is well-stated. In addition to describing the algorithm, some intuitions behind the algorithm design are provided in the paper.", "weaknesses": "- The main weakness is that the experimental evaluation is missing. The paper would be strengthened if an experimental section were added.", "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": "6m4e9XhuAQ", "reviewer": "Reviewer_8uCJ", "summary": "This work considers a federated Q-learning for tabular episodic MDP, where multiple agents collaboratively explore the environment and learn an optimal Q-value with the aid of a central server. They proposed two federated Q-learning algorithms (FedQ-Hoeffding, FedQ-Bernstein) with event-triggered policy switching and synchronization. The algorithms provably achieve linear regret speedup while requiring communication cost logarithmically scaling with the total number of samples (T).", "questions": "* The previous federated Q-learning literature [1] already showed that communication cost logarithmically scaling with T is achievable without using event-triggered synchronization (with fixed communication period). Is there any reason to introduce event-triggered synchronization especially in this setting?\n* The algorithm seems to fix the Q-values and behavior policies to be the same for all agents during local iterations. However, a setting that agents can flexibly change their policy based on their local observations before the next synchronization seems more natural to me, especially in the federated setting. Would it hurt the performance if they can change their policies and Q-estimates locally during local updates? I wonder if letting agents to change their policies can introduce some diversity in their exploration, which might be an advantage in learning.", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- They proposed a federated Q-learning algorithm with event-triggered synchronization, which  guarantees logarithmic communication cost in terms of T.\n- They provided a finite-time regret analysis on the federated Q-learning algorithm with policy switching and proved linear regret speedup.", "weaknesses": "* Although the algorithm considers a setting that agents can collaboratively explore by changing their policies, the algorithm requires all agents to use the same fixed policy during local iterations, which seems to be quite restrictive. It would be nice if you could elaborate on the necessity of these restrictions.\n* Although the paper claims that the event-triggered synchronization method is a key to reducing communication costs, the order of communication costs they showed in this paper seems to be larger than the one shown in [1], which uses just a fixed communication period. The communication cost shown in [1] not only logarithmically scales with T, but also is more efficient in terms of other factors (M: number of agents, $(1-\\gamma)^{-1} (\\approx H)$: length of horizon). I understand that direct comparison might be difficult given the settings are different, but I’m still not convinced that the communication cost shown in this paper is especially low. It would be nice if you could provide more detailed comparisons with recent literature to help better understand on the communication efficiency.\n\n[1]: Jiin Woo, Gauri Joshi, and Yuejie Chi. The blessing of heterogeneity in federated q-learning: Linear speedup and beyond. In International Conference on Machine Learning, pp. 37157–37216, 2023.", "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": "2MeDD0cmQk", "reviewer": "Reviewer_dPut", "summary": "This paper studies the federated RL and proposes two model-free algorithms---FedQ-Hoeffding and FedQ-Bernstein---that achieve regret speedup and low communication.", "questions": "- Why define $\\tilde{C}$ as it is used only once (above Eq. (2)) in the main paper? \n- Case 1 at Page 5, it should be $\\eqqcolon i_0$ instead of $\\coloneqq i_0$.", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Overall, this paper has a fair contribution. It proposes two federated RL algorithms with a regret speed up and logarithmic communication.", "weaknesses": "It would be great if the authors could provide some empirical validations for their algorithm. I understand this is a theoretical work, but it is always helpful to corroborate the theoretical results with some experiments.", "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)