Regret-Optimal Q-Learning with Low Cost for Single-Agent and Federated Reinforcement Learning
Authors: Haochen Zhang
Zhong Zheng
Lingzhou Xue
Venue: NeurIPS 2025 poster ()
Keywords: Reinforcement Learning
Federated Learning
Regret
Policy Switching Cost
Communication Cost
Primary area: reinforcement_learning
TL;DR: We propose novel model-free RL and FRL algorithms, which simultaneously achieves the best-known near-optimal regret, a low burn-in cost and a logarithmic policy switching cost or communication cost.

Abstract: Motivated by real-world settings where data collection and policy deployment&mdash;whether for a single agent or across multiple agents&mdash;are costly, we study the problem of on-policy single-agent reinforcement learning (RL) and federated RL (FRL) with a focus on minimizing burn-in costs (the sample sizes needed to reach near-optimal regret) and policy switching or communication costs. In parallel finite-horizon episodic Markov Decision Processes (MDPs) with $S$ states and $A$ actions, existing methods either require superlinear burn-in costs in $S$ and $A$ or fail to achieve logarithmic switching or communication costs. We propose two novel model-free RL algorithms&mdash;Q-EarlySettled-LowCost and FedQ-EarlySettled-LowCost&mdash;that are the first in the literature to simultaneously achieve: (i) the best near-optimal regret among all known model-free RL or FRL algorithms, (ii) low burn-in cost that scales linearly with $S$ and $A$, and (iii) logarithmic policy switching cost for single-agent RL or communication cost for FRL. Additionally, we establish gap-dependent theoretical guarantees for both regret and switching/communication costs, improving or matching the best-known gap-dependent bounds.

Regret-Optimal Q-Learning with Low Cost for Single-Agent and Federated Reinforcement Learning
Haochen Zhang Zhong Zheng" Lingzhou Xue Department of Statistics, The Pennsylvania State University {hq25340, 2v253337 lzxue> @psu. edu
Abstract
Motivated by real-world settings where data collection and policy deployment- whether for single agent across multiple agents-are are costly, we study the problem of on-policy single-agent reinforcement learning (RL) and federated RL (FRL) with a focus minimizing burn-in costs (the sample sizes needed to reach near-optimal regret) and policy switching or communication costs. finite-horizon episodic Markov Decision Processes (MDPs) with S states and A actions, existing methods either require superlinear burn-in costs in S and A or fail to achieve logarithmic switching communication costs. We propose two novel model-free RI. that the first in the literature simultaneously achieve: (i) the best near-optimal regret among all known model-free RL or FRI. algorithms, (ii) low burn-in cost that scales linearly with S and A, and (iii) logarithmic policy switching cost for single-agent RL or communication cost for FRL. Additionally, we establish gap-dependent theoretical guarantees for both regret and switching/oommuicatiin costs, improving or matching the best-known gap-dependent bounds.
parallel
Saaiiinss---aaa-Seeeeeeeeeee CowCost and Fed(Q-aallySettler
Introduction
Reinforcement Learning (RL) [78] is subfield of machine learning focused on sequential decision- making. Often modeled as a Markov Decision Process (MDP), RL tries to obtain an optimal policy through sequential interactions with the environment. It finds applications in various fields, such as games [73, 74, 75, 82], roboties [32, 45), and autonomous driving [101]. We assume the presence of central server and M local agents in the system. Each agent interacts independently with an episodic MDP consisting of S states, A actions, and H steps per episode.
In this paper, we focus on model-free online RL and federated RL for tabular episodic Markov Decision Processes (MDPs) with inhomogeneous transition kernels, consisting of states, A actions, lower bound for any tabular MDP and any learning algorithm is 2( (H2SAA) where T denotes the total number of steps [37]. The model-based algorithm UCBVI [9] first reaches this lower bound up to a logarithmic factor. Model-free algorithmss conntthmms--mmnllly called Q-learning- are widely used in practice due to their simplicity of implementation and lower memory requirements [37]. Specifically, model-based methods typically require memory that scales quadratically with the number of states S for storing the estimated transition kernel. Model-free methods require memory that only scales linearly with S but generally face greater challenges in achieving comparable regret.
and Н steps per episode. It is known that the regret information-theoree
[37] proposed the first two model-free algorithms with theoretical guarantees: both attaining subopti- mal regrets compared with the information-theoretic lower bound. [10] modified their algorithms
"Equal Contribution.
t Corresponding Author.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

and further reduced the number of policy updates, also known as the switching cost, to a logarithmic dependency on T. Later, [111] proposed UCB-Advantage that reaches the near-optimal regret of O(VH²SAT) and a logarithmic switching cost, but it comes with a large burn-in cost: the regret upper bound is valid only when T 2 O ( H22). Here, O hides logarithmic factors. To mitigate this, [50] introduced the near-optimal Q EarlySettled- -dvvattaa algorithm, which significantly re- duces the burn-in cost to O(SAAt")) scaling linearly with S and A. However, this improvement comes at the expense of a high switching cost that scales linearly with T. Thus, UCB-Advantage and Q-EarlySettled Advattage suffer notable limitations: the former requires a large burn-in cost, and the latter fails to achieve logarithmic switching cost. This raises the following open question:
Is possible that a model-free RL algorithm achieves the near-optimal regret Ö (VHSSAT) with burn-in cost that scales linearly with S, A and a logarithmic switching cost simultaneously?
In many real-world scenarios, an individual agent faces significant limitations in data collection, and agents can jointly learn an optimal policy, thereby improving the sample efficiency. This naturally motivates the framework of Federated Reinforcement Learning (FRL) that leverages parallel explorations across multiple agents coordinated by a central server. FRL enables faster learning while preserving data privacy and maintaining low communication costs, defined as the total number of scalars shared among the central server and the local agents. The regret wefoormation-thoreeeee lower bound for any tabular MDP and any FRL algorithm with M agents naturally extends to ((VMH2 where T denotes the average number of steps per agent. Among existing methods, the only model-based FRL algorithm that matches this lower bound (up to logarithmic factors) is review model-free algorithms for which the communication cost scales logarithmically with T. [113] proposed the first two model-free FRL algorithms with suboptimal regrets. [114] introduced FeedQ-Avvnttage that attains the near-optimal regret bound of Ö(V H AT') with high burn-in cost of OM 12). Thus, it is natural to ask the following question for the federated setting:
VeI-UCBVI [46]. In the following,
it possible that a model-free FRL algorithm attains the near-optimal regret Ö / M MH'SAT) with burn-in cost that scales linearly with 8, A and a logarithmic communication cost simultaneously?
These two questions are challenging due to several non-trivial difficulties. First, the Q- Q-aarlySettled- Advantage algorithm [50] updates its policy after each episode, incurring a switching cost that scales linearly with T. While this algorithm demonstrates low burn-in cost in single-agent scenarios, its effectiveness in federated learning settings remains unknown in the literature. Second, while UCB- Advantage [1 [1]]] and its federated extension Fed(-Advantage [1 14] leverage reference-advenn advantage decomposition to reach near- optrmml regrets, neither incorporates Lower Confidence Bounds (LCB) to settle the reference function like Q-FartySentee--AAvvatge.. Thus, their burn-in costs exhibit superlinear dependence on S and A.
To simultancously achieve logarithmic switching/oommunicttionn costs while maintaining low burn-in costs, an algorithm must satisfy two requirements: (1) infrequent policy updates rather than per- episode updates, and (2) proper incorporation of LCB methods. This creates a fundamental trade-off: while delayed updates reduce switching and communication costs, their combination with LCB methods inevitably introduces additional regret and reference function settling errors. Bounding them with the reference functions introduced in [50, 111] involves controlling a weighted sum of a sequence of random variables, where neither the weights nor the random variables adapt to the data generation process. As a result, standard concentration inequalities cannot be directly applied to this type of non-martingale sum, presenting key challenge in extending the framework simultaneously achieve low burn-in costs and logarithmic swiching/communicaion costs. Prior techniques, such as the empirical process [50] that accommodates non-adaptive random variables and round-wise approximation methods [105, 1 13, 1 14] that handle non-adaptive weights, are insufficient when both forms of aon-adaptissness coexist.
Summary of Our Contributions. We answer the two open questions affirmatively by proposing the FRL algorithm Earte-yyyySeetee-Lowwwww LowCost for the case when M = 1. Our main contributions are summarized as follows:
and its single-agent counterpart Q-EarlySettled-
(i) Algorithm Design:
We propose the first round-based algorithm for single-agent RL that achieves logarithmic switching cost, advancing beyond traditional per-episode updates. For FRI,, we in- troduce the LCB technique for the first time to attain a low burn-in cost. While the logarithmic

---

switching/oommuiittioon cost entails trade-off that slightly increases regret, our use of a refined bonus term term-while maintaining optimism- -iields
-iields improved regret performance over Q-EarlySettled- Advantage [50] and FedQ-Advantage [114], the current state-of-the-art algorithms for provable model-free single-agent RI. and FRI., respectively.
(ii) Best Regret Performance: In both single-agent RL and FRL scenarios, our algorithms achieve the best-known regret bounds among existing model-free approaches. In the single-agent RL set- improves upon Q-EarlySettled-AAvaaae
ting, Q-EaalySSetled-LowCCo literature by factor of (ST)). This is a significant advancement, logarithmic factors in T are known to be crucial for practical performance [68, 109]. For the FRL setting, compared with the existing state-of-the-ars algorithm FedQ-Advantage FedQ EarlySettld----oo LowClsst eliminates superlinear dependence on S and A. It is significant for large-scale applications such as text- based games [13] and recommender systems [19]. Numerical results in Appendix B demonstrate that our algorithms consistently achieve the lowest regret.
best method in the
(iii) Simultaneous Low Burn-in Costs and Logarithmic Sratching/Commmnicllti
Costs: Our algorithms achieve low burn-in costs that scale linearly with S and A, while maintaining logarithmic wwiching/oommunication costs. In single-agent RL, --EarlySetled-LooCCoo
simultaneously (I) reduces the burn-in cost ÓSS AH which linearly depends S and A, representing a significant
improvement over the burn-in cost Ö(5 2222) UCB-Advantage and (2) maintains logarithmic switching cost that outperforms the linearly scaling cost of Sarryyeetled-AAvvataaee Similarly, in (1) reduces the burn-in cost O(MS (MSAHl)) compared with OMS A 2 for FedQ-Advande Advantage; and (2) maintains logarithmic communication cost.
the FRL setting, FedQ-Early EallySyttytttee-LoowwCoo
In Table and Table 2, we compare Q-EarlySSttled-LLo Lowst with existing model-free single-agent RL algorithms, and FedQ-Farty Saryy-eeeetteeddd---- LowCsst with other model-free FRI approaches. The results further demonstrate that our algorithms are the first to simultaneously achieve the near-optimal regret, low burn-in costs, and logarithmic
costs in both single-agent RL and FRL.
Table I: Comparison of model-free single-agent RL algorithms.
Near-optimal regret
Logarithmic switching cost
Algorithm (Reference)
Low burn-in cost
UCB- HCB-Hooffding [37]
X
X
X
UCB-Bernttein [37]
X
JJCB--Hoefding [10]
X
X
UCB2-Bernstein [10]
X
X
UCB-Advantage [111]
X
Q-
-aallySeteed--dvaataae [50]
X
Q-FarlySSetedd-LoooCoot (this work)
Table 2: Comparison of model-free FRL algorithms.
Near-optimal
Logarithmic communication cost
Low burn-in
Algorithm (Reference)
regret
cost
FedQ-Hoefiding [113]
X
X
FedQ-Bernstein [113]
FedO-Advvnntaee [114]
Tedd@-EarlySeeteeeLLoCCCS (this work)
We present gap-dependent analyses in both single-agent RL and FRL settings for MDPs with positive suboptimality gaps [84, 102]. For the single-agent RL setting, we establish the first gap-dependent switching cost bound for algorithms employing LCB techniques, while simultaneously achieving the best gap-dependent regret matching that of Q-Early Advantage [1 15). In the FRI. setting, our algorithm not only matches the best known communication [105], but also provides improved gap-dependent regret guarantees, advancing beyond the only existing results in [105].
(iv) Gap-Dependent Results:
cost bound of
3

---

To integrate the LCB technique with the round-based design for achieving simultancous low burn-in costs and logarithmic swiching/commuiiction costs, we address the challenge of non-adapriveness in controlling the weighted sum through the surrogate reference function used in Lemma I.3 when approximating the non-adaptive random variables. It simplifies the problem to the case that only the weights show non-adaptiveness, allowing us to apply round-wise approximations to bound the weighted sum. It facilitates the proof of the regret theoretical guarantees while yielding strictly improved regret bounds. Details can be found in Appendix C.
(v) Technical Novelty:
2 Background and Problem Formulation
2.1 Preliminaries
Tabular Episodic Markov Decision Process (MDP). A tabular episodic MDP is denoted as M == (S,A, A. H,P,, ..P,r) r), 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, F := { 1 h==1 1 fa=
is the heterogencous transition kernel so that (- s, a) characterizes the distribution over the next state given the state action pair (s, a) at step and r : {ra]mm collects deterministic reward functions on S x A with each bounded by [0, 1].
In each episode, an initial state $1 is selected arbitrarily by an adversary. At each step h E [H] (1.2....,H) H). an agent observes a state S/ E S, picks an action as E A., receives the reward Th = Th (s,; an) and then transits the next state 81+1- The episode ends when absorbing state 811+1 is reached. For convenience, we denote Ps.a, = PengsrPa((le.a (f(*++1) 1)1:: = On = a), 1,f= = f() and V (f) = Ps (IP ff) for any function f S + R and triple (s, a, h).
Policies and Value Functions. A policy π is a collection of H functions { S + A he(!!
where A is the set of probability distributions over A. A policy is deterministic for any 8 E S, (s) concentrates all the probability mass on an action a E A. In this case, we denote T (s) a.
Denote state value functions VIT S 5 E by
H Es (P.))) (sw, shh = s]
(s) = Σ
b'=h
and state-action value functions Q7
S x +
by
H
(7 = (s) +
Σ M==++1
E (w) [Tw (sw, an)) 88 = 8, = a]]
For tabular episodic MDP, there exists optimal policy x* such that (s) = sup, (s) V (s) for all (s, h) E S [H] [9]. Then for any (s, a, h) E S x Ax x [H]. the Bellman Equation and the Bellman Optimality Equation can be expressed as:
(s) = Ea (s) (s) (s,(s,)))
(s) = max (s, (s. == (s, a) + Pe.a Vitt
Q7 (s.a) = (s, P. Psaah Vit T+t and
(I)
V ( (5) V,, a, h)
(8) (s) 0, V(s, a, h).
Suboptimality Gap. For any given MDP, we can formally define the suboptimality gap follows.
Definition 2.1. For any (s, a, h), the suboptimality gap is defined as An(s, a) = Vs) Q% a).
Equation (1) implies that for any (s, a, h). (s a) 2 0. We then define the minimum gap: Definition 2.2. We define the minimum gap as A min := inf[ (s) (s) > 0, V(s, a, h)}.
We remark that if (sn a) An(s, a) > O, V(s, a, h)} 0. then all actions are optimal, leading to degenerate MDP. Therefore, we assume that the set is nonempty and Amin > 0. Definitions 2.1 and 2.2 and the non-degeneration are standard in the literature on gap-dependent analysis [76, 96, 98].
Switching Cost. Similar to [68], the switching cost' is defined as follows:
Definition 2.3. The switching cost for an algorithm with U episodes is Nswitch := ΣV u[ o r". Here, nO is the implemented policy for generating the u-th episode.
'Soee works name global switching cost and also analyzes the local switching cost defined as Nowinh == VV-1 E.,, [=))-(()) o (s)) [10. 111] proved the same cost upper bound under both definitions.

---

2.2 The Federated Reinforcement Learning (FRL) Framework
We consider an FRL setting similar to [113, 114], where a central server coordinates M agents, each interacting with an independent MDP. For agent m, let Un be the number of episodes, "h, the policy used in episode u, and sTt." the initial state. The regret over T H >m= Um total steps is
M Un
(T)
ΣΣ m==
V/"" (siT..)
(2)
Here, T : T/M is the average total steps for M agents. When M 1, Equation (2) also defines the regret for single-agent RL, where I' represents the total number of steps in the learning process.
The communication cost of an FRL algorithm is defined the number of scalars (integers real numbers) communicated between the server and agents.
Algorithm Design
3.1 Algorithm Details
Now we present FedlQ-FarrySSetteaaLowCCC Cost,,, our model-free FRL algorithm with M agents, along with its single-agent variant (when M = 1), Q-EaalySetlcc-LooCoos
runs in rounds indexed by E {1, 2, K}. where each agent m performs n= episodes in round & (to be defined later). This formulation naturally accommodates a common form of system heterogeneity [52], referred to as heterogeneous exploration speed. It allows agents to explore the environment at different rates and generate varying numbers of episodes in each round. This type of heterogeneity is commonly considered in model-free FRL studies [113, 1 114], which is distinct from the environment heterogeneity considered in [46].
m.kkk. m.kkk } For episode j in round k, define the trajectory collected by agent m as {(5% ,a ,Th ".*(s,, a) denote the number of times that agent m visits (s, a) at step h in round k. n (8,a) m.,k Em nh (s,a) a) and ( a) - n (s, a). We omit (s, a) when there is no ambiguity.
Let n (ss
Define V/2 Q% l and viR.k as the estimated V- -function,, the estimated Q --funccion, the lower bound function and the reference function at step h at the beginning of round k. Specifically, @h + VI. H+1 V = O. We also define the advantage function as AA, V V.R.A. At the beginning of round k the central server maintains N policy n² [m))) and four other a),
quantities for any (s, a, ht:: Hh R.k (s)a), oh & (s, P4 A.* (s, a) and of A.k (s, a) (all zero-initialized when
1), which will be explained later. We then specify each component of the algorithms as follows.
Coordinated Exploration. At the beginning of round k. the server broadcasts n², along with
{N* 7 (s)), Vi (s), V/ (s))(s)),. to all agents. Here, Q₁ Vi V...1 H, V NA = 0 for any (s, a, h) and x² is an arbitrary deterministic policy. Each agent will then collect mi,k trajectories under the policy n²
Event- -ring-Triggere Termination of Exploration. Similar to [113], in round k, for any agent m, the end of each episode, if any (s, a, h) has been visited by ch(s,, times, then the exploration for all agents will be terminated. This trigger condition guarantees
1/b m. (s, < (s, max (1,
+1) [
N (s,a)
} V(s, (ss,ahh,))
MH +
and there exists at least one tuple (s, a, h, m) such that the equality holds.
Local Aggregation. For any visited (s, a, h) with a =*) agent m computes the follow- ing six local sums over all next states of visits to (s, h) and send these local sums along with fra(s, Th (s)), ni mitk (s. (K))) hn to the central server at the end of round k.
[U bink m.kk Phe ohe m.kk m..k (s.a)
m.
Σ V vL.k PRk (22,)), vaLs (VAA))) (smuhh)) I [(8) (sttiks a am.k) = (s.0)) (4)
5

---

Central Aggregation. After receiving the information, for any visited (s,a.h) h) with a = (s), the
central server computes n >m Bh m,kk
N N + nyt and six round-wise means:
oh l.k r.k r.k a.k a.k uh Uh Th Ph oh
(b, Σ
Un Una Whi Pha Tha //h(l,a). (5)
m.kk m.k mik m.k mikk m.kk
also updates two global means, Ph
R.k R.k+1 (s, a) and 0% p (),,),.s as
(14 R.k+1
(s, a) () [ (4h ohh (s, a) + m (ri* of (s. (s. a)) /
(s, a), (6)
which is the historical mean of the reference function and the squared reference function over all next states of visits to (s, a, ht) in the first & rounds.
nh) for any 1 S i S E N+. with of = and vó 0. We also define (11, n2) II (L (1-1) ne) for any ni S n2 E N+ and the learning rate aa = 1 - (NV 1, Here, na is a simplified notation depending on (s, h, k). Then, for any visited (s, a, h) with (s), the central server updates the estimated f-uunction as follows:
Define 7/+ =
#+1 and va 1 I[ H+C
2 ( a) = min {0h [ot (s, aa, Q (s, a), ())
(7)
Here, for each (s, a, h). the Hoeffding ttpe Q-estimate Q) U.+++ [37, 113] and the Reference- Advantage-type @sttimate 2h [50, 111] are updated according to the following two cases:
Case 1: N (8) < 2MH H + =: ig- In this case, Equation (3) implies that each agent can visit (s, a, h) most once. Denote 1 S m1 ... m S M as the agent indices with ni (s, a) 1. The central server first updates the two global weighted means of the advantage function V and the squared advantage function (V/44)2 over all next states of visits to (s, /1) as:
A.t+1) ) (8, (1 mw of (s, (AA oh
Σ nxr (Pha hha (s, (8)
The UCB-type. LCB-type [50] and the reference-advaattge--yy Q estimates are updated as follows:
Qu (s,a) = (1 (1- - (s, + (s
+
M U to (s, + Bl (s) (9)
No+1
t=1
L.++l (s, (1-)))) ) (s.
nora(s,a)
" U +c hh!
wkt1 my
- (8, - Bl+t1 (iitt(s,a) (s. (10)
c = -1- +n (ra t RA++1
Nkl1 me.k Ux (%
-hh m) 1 (s, a). (11)
Case 2: (1 a) 2 in. In this case, the server updates the two global weighted means as
(MÂ (utt oh A.++1) (s. (s. a) (1 (1- (1- (MA A (s,))ss,)) a) + na (M o (s, ( a).
(12)
Now the three Q estimates are updated as follows:
Qu u.A+1 (s, a) = - 1 (s, + na (rn(s, a) + u a)) + B x (s,
(13)
2 (s, (s,a)=
=(1 (10)==1mp)))) no0 (s, a) + Ta (r((nsss a) L.k (s, a)) - B (s,a).
(14)
(s, = (1 1111))0tht (s) - no [n + Mh
RK+1
+ t 1/ ( (8, + Bhh gR
x
(8.a).
(15)
In both cases, the cumulative bonuses are given as:
N++1
N
B (s,
Σ
n No by
B BR (s,
Σ
T
N
i (s,
(16)
N= +1
N

---

where b, = co / for sufficiently large constant cs and positive constant determined later, and n. a) is computed as follows. For sufficiently large constant c/ the central server calculates
gR.kt 55 a) = R
Von
R.E+1
(4h ( + V VVll(
(H(( A (1
Then for sufficiently large constant
R.2 %
0 and & (N%, No let bR 3ha + t F22H22,
12/ and
BR K..N (1 - 1/ 3 R + ph gR.
/ + +.b
R.2 H2 //N
After updating the estimated Qffunction, the central server proceeds to update 1 and ih (s) for each (s, h) E S [H] as follows:
(s), h (2l,tt(ss)
(s) max 2ht d'EA
+++ (s,a', Vil (s) max max 2h
(17)
"h (s) = arg max 2h (s,d'). a'EA
(18)
Finally, for any state-step pair (s,h). the central server updates the reference function as VA VR,++1 (s)
vk+1 (s) if either: (1) v (s)
v (s) > 3, or (2) it is the first round where V V (s)
Vn vI. (s) S B for predefined E (0, H.. Otherwise, the server settles the reference function
by Vil tRt (s) = -/ih'(s) In this case, the settlement is triggered after the condition V/ (s)
h
(s) S 3 first holds for some round as guaranteed by the monotonically non-increasing
property of (x) 1 (s) established in Equation (7) and Equation (17). The algorithm then proceeds round & 1. Algorithm 1 and Algorithm 2 formally present the algorithms. For reader's convenience, we provide graphical illustrations and two notation tables in Appendix D.
Algorithm FFelO-EarySSetteee--ooCCCCC (Central Server)
1: Input: To E N4.
2: Initialize k: 1, Q (s,a) a) 0h (s,a) a) (s) (s) H. Q (s,
U.
V/ (8) = -N a) = 0, un (s) = True, a() E Ax [H] and an arbitrary policy IT
3: while EHH E., (s, To do
4: Broadcast n², (N (+))),, (V) (VL..
(8) and (s)) a. to all agents. 5: Wait until receiving a termination signal and send the signal to all agents.
6: Receive the information from clients and compute round-wise means in Equation (5).
7: for any (s, a, h) E S x Ax [H] do
8: if ( a) = 0, then Q (s, + (s)
else Update Qh (s, a) via Equation (7)
9: end for
for any (s E S [H] do
11:
Update Vi v-+ (s). h
vL,k+1 (s) and Th
(s) via Equation (17) and Equation (18).
if V (s) v... v (s) > B, then v RRA ((s) v (s).
12:
R. else if uh (s) True, then VR (8) = v (s). up
R.k+1
(s) False.
end if
end for
14: k + k k+1.
15:
end while
3.2
Intuition behind the Algorithm Design
UCB and Reference-Advantagee Decomposition with Refined Bonus. Similar to [50, 114], we adopt two techniques-upee confidence bound (UCB) exploration with the bonuses in the esti- mated Q- Q-function and reference-advantage decomposition- attain the near-optimal regret bound. To further improve regret performance, we refine the bonus term B used to update the esti- mated Qffunction by removing its dependence on (N/)3// [50, 114]. This refinement enables

---

Algorithm 2 FeceQ--Eanrlyeeettll-oooWCoCCC (Agent m in Round k))
1: Initialize "i 1/ 1h1 - Mhi =
Ri Ph. hha = O, V(s, h)) E A [H].
2: Receive n², (N% (8, (,)) (..) (s))
(8) (v) and (v/ (8))an
3: while termination signal from the central server do
4: while ni
(a.a) ni"(s, (8, a) < max { MH(H+T]
(ss,a, E S Ax [ do
5: Collect new trajectory {(s,: On Tn)
rn)m M=1 with an = (s)).
6: For any h E [H], nh (sp, on) 1 and (u% "he phas his pha The (sp, 1
(V VLL V.R.A. (vh+1) vAk 1441
7: end while
8: Send a termination signal to the central server.
9:
end while
10: For any (s, E ES x [H] with (s),
(nip .uh 1a .ang hhr -Pi, (oma)) ) a) & (n% : 1h hhd Pliy hhr Pha oa (s) m.kk m.k mack makk makk mik oh (s, (+))) 11: For any (s, h) E S x [1f], send {Tr, nh Uh Und Mag hhe Mha hh
m.kk mn,k mn,
algorithms to outperform both SaaalySettedd-AAvanaaee in the single-agent RL setting and FedQ-Advantage in the FRL setting.
LCB for Early Settlement of the Reference Function. Compared with UCB-Advantage and FedO-Advantage, our algorithms incorporate Lower Confidence Bound (LCB)-type estimate Qli* VLL derived accordingly serves as a lower bound of VK, while V, is an upper bound for V since O 2 Q by the UCB-design. To obtain an accurate reference function V, we aim to settle the reference function L by V² when V Vi S 33 for the first time. Both UCB-Advantage and FedQ-Advantage settle the reference function at a given (s, h) after has been visited sufficiently often-when the number of visits reaches a threshold (3(3). This is rather conservative condition, resulting in a large burn-in cost. In contrast, the LCB technique guarantees that Ví E [V/L-A V enabling an early settlement when V VL, < 3, which consequently achieves a low burn-in cost.
Svent-Triggered Termination and Infrequent Policy Updates. Our algorithms switch policies infrequently, as estimated f-function and policies are updated only after each round ends due to condition (3). This design ensures that visits to each (s, a, h) grow at controlled exponential rate across rounds, enabling logarithmic bounds on switchingcoommunicttoon costs.
4 Theoretical Guarantees
When M = 1, the Seno--EalySStteed-Loweee EarlySettled-LowCCoo by eliminating the central server and the agent-server communication process. In this section, we present the theoretical performance of our algorithms in both single-agent RI and FRL settings. We first set the constant = Ti is a known upper bound of the total steps f' as defined in (b) of Lemma F.I.
algorithm reduces to its single-agent variant, Q-
where p E (0, 1) is the failure rate and
4.1 Worst-Case Guarantees of Q-EartySetlled-LoooCos
We now present the worst-case results for Q-FarlySettled-LLooCor It achieves the best regret among all model-free single-agent RL algorithms with a low burn-in cost and a logarithmic switching cost.
Theorem 4.1. For any p 10, let to = log(SAT/p). Then for Q Q-FaaryySetedd-aawooo (Algorithms/ and 2 with M = and B E (0, H), with probability at least 1 - p. we have
Regret(T) (T) < (1(1111)))) / H SAL/3).
HSSAT
Setting 3 @()), when T O(SAHL)), the regret bound matches the lower bound O(VH2SAT) up to logarithmic factors. Next, we compare our algorithm's performance with two near-optimal algorithms: UCB- (CB-Advantage [111] and -aaalySettled-Avaaaee [50]. UCB-Advantage has

---

regret of O(VH'SAT + 5 (3/3//2/1/4 and burn-in cost of Ó(S H2* while our algorithm achieves lower regret with only linear dependence on S, A and better dependence on H, and much smaller burn-in cost with only linear dependence on S A. Compared with Q-EarlySettled- Advantage, our algorithm further improves the regret bound by a factor of log (og(SA7) (SSAAA/) AT)p) and shows better regret in the numerical experiments in Appendix B.1 due to the refinement of the cumulative bonus Bh BR,++1 in Equation (16), and the of the surrogate reference function in the proof.
Theorem 4.2. Let Č = HH + 1)SA. For Q-FarlySeuted-Lowwe Low (Algorithmss and 2 with M = 1 and B E (0, H). the switching cost is bounded by max + 4C log(TT/)),3)
When T > ed C, our algorithm achieves a logarithmic switching cost of O(H"5AAlog
4.2 Worst-Case Guarantees of VedQ--EarySSetteelLLow.Co
We now discuss the worst-case results for Eee-lSSettled-LLwwee among all model-free FRL algorithms with a low burn-in cost and a logarithmic communication cost.
It achieves the best regret
Theorem 4.3. For any p E (0, 1), let (1 log(MSAT) AT/p). Then for FedQ- FarlySenled--wwwoor (Algorithms and 2 with 3 E (0, H),, with probability at least - p. we have
RTgret(T) So ( (1+ (1+ (1+9W/MHSSATRR H
+ MH
B
Appendix I provides unified proof for Theorem 4.1 and Theorem 4.3. Setting 3 = (1), when T > O(MSAH1)), the result becomes ((MMH2 AT), matching the lower bound with total of MT steps. Compared with FedanAavantage [114] with a near-optimal regret bound O(MMHSSAT M 3 SAT' + 7 5 A² ), our method achieves lower regret with milder dependence on H. S, A. Furthermore, FedO-Advantage requires ((M53 12) samples to reach near-optimality. while our method only needs Ö (MSAAF20) with a burn-in cost scaling linearly in S, A. Numerical experiments in Appendix B.2 also demonstrate that SettEarrlSSetted-Lovveee regret performance among all model-free FRL algorithms.
achieves the best
Proving the worst-case regret bounds in Theorems 4.1 and 4.3 is challenging due the technical difficulty of double von-adaptiveness, and we overcome by the novel use of a technical tool, the surrogate reference function. Please refer to Appendix C for more details. Next, we diseuss the worst-case communication cost results of FedQ-Early Early
Theorem 4.4. For FedQ- Early-aaaaeeee--ooooooo (Algorithm I and Algorithm 2 with B E (0, H), the number of rounds is bounded by max (2MC + 4MC AMCCog(T/C) 3MC).
Appendix presents a unified proof for Theorem 4.2 and Theorem 4.4. When T > e C. we have As each round incurs O M HSS) communication cost, the total cost is
K < SHSHAA O(M" A log(T)) growing logarithmically with T. If agent waiting is permitted, synchroniza- tion in each round can be delayed until all agents satisfy the trigger condition in Equation (3), similar to the setting in [114] when the optimal forced synchronization disabled. In this case, the number of rounds K can be bounded by max - 4C log(T/C), 3MCJ. which is independent of M.
(T)) (olgo)(T))
4.3 Gap-Dependent Guarantees
This section provides gap-dependent results under both single-agent and federated settings. We define the maximal conditional variance Q* := maxs,a.1 { (Vitt))))t)) [0, H!] [102]. Theorem 4.5 establishes the best-known gap-dependent regret for model-free RL, matching that of Q-EarlySettled- Advantage in [115], while maintaining a logarithmic switching cost.
Theorem 4.5. For -EarlySemled-LooCae (Algorithms/ I and 2 with M and 3 (O,H),
E (Regret(TT) < (Q* + H
H SA
A
Amin
3
Next, we present the gap-dependent switching cost results under the same assumptions as [105]: full synchronization, random initialization, and G-MDPs. We first review the initial two assumptions:

---

(I) Full synchronization. Similar to [113], we assume that there is no latency during communications, and the agents and server are fully synchronized [60]. This means n mi. n for each agent m.
(II) Random initializations. We assume that the initial states (s J...j.m are randomly generated with some distribution on S, and the generation is not affected by any result in the learning process.
Assumption (I) implies that all agents have the same exploration speed. We now introduce G-MDPs. Definition 4.6. A G-MDP satisfies the following two conditions:
(a) The stationary visiting probabilities under optimal policies are unique: if both x x²* and π n are optimal policies, then we have IP (sh, =s(m=:1) = (sh- ss/= s|xx ) =: P,,
(b) Let (s) {a
0, then arg max,'' Q7, (s.s)))). For any (s, S [H] P
[A [s)] 1, which means that the optimal action is unique.
G-MDPs represent MDPs with generally unique optimal policies. Compared requiring a unique optimal policy, G-MDPs allow the optimal actions to vary outside the support under optimal policies, Le., the state-step pairs with P+ = 0.
For any G-MDP, we define Cst min | 8 E S. PH, 0}, which reflects the minimum visiting probability over the support of the optimal policy.
With these assumptions, we now present gap-dependent switching cost bound for the S-tarlySettled- LowCost algorithm. This result fills a notable gap by providing the first such bound for LCB-base algorithmss, and it matches the best-known gap-dependent switching cost guarantee of the single-agent feefdngg algorithm [105], which, however, suffers from higher and suboptimal regret.
Theorem 4.7. For any p E (0, 1). let to log( SAT). Then for E-EarlySented-Love rithms I and 2 with M 1 and 3 E (0, H), under the random initialization assumption and G-MDP, with probability at least 1 - p, the switching cost is bounded by
(Algo-
p
o H S
11 A1
log (
(1) Cst
T
+
3A min
HSA
Theorem 4.8 and Theorem 4.9 present gap-dependent results for FedQ- EereySyattylle--oooee Theorem 4.8. For FedQ-Early HarlySetteed-Loooost (Algorithms) and 2 with B E (0, H)) let 12 log( (S)))), then we have
E (Regret( SO (Q'' (
(Q'+8H))HSAP S
+ +H
Amia
B
Appendix gives a unified proof for Theorem 4.5 and Theorem 4.8. Compared with the only federated gap-dependent regret bound ( Ann Aiin + H SAVL) established for TedQ-Hoeffding in [105], Theorem 4.8 improves the dependence on Amia by factor of H for the worst scenario, where Q+ = O(H²), Furthermore, in the best scenario when the MDP is deterministic and O+ 0, our
bound scales as Ö( min for specific B, improving upon the linear dependency.
Theorem 4.9. For any p E (0, 1). let 1 = log( MSAT). Then for FedQ- EarlySettled-Lowe LowCoss (Algorithms and with 3 E (0, H)) under G-MDP and the assumptions of full synchronization and random initialization, with probability least p, the number of rounds K bounded by:
o M log (MHg) + 5
H H*SA
SA
+ SHSSSog
(1)
log
T
3A
Co.
HSA
Appendix L. gives unified proof for Theorem 4.7 and Theorem 4.9. This result matches the only gap-dependent upper bound on the number of communication rounds, established for [105]. while our algorithm simultancously achieves a better and near-optimal regret.
5 Conclusion
We propose two novel model-free algorithms, Q-EaarySetteed-LowCorr and Fede--arlySetttedd LowCost, that simultaneously achieves the near-optimal regret, a low burn-in cost that scales linearly with 5 and A, and logarithmic switching/communicaion cost. Technically, we combine LCB and UCB with reference-ade reference-advantage decomposition for more efficient reference function learning.
10

---

Acknowledgment
The work of H. Zhang, Z. Zheng, and L. Xue was supported by the U.S. National Science Foundation under the grants DMS- RMS-1153188 and CCF-2007823 and by the U.S. National Institutes of Health under the grant IROIGM152812.
References
[1] Alekh Agarwal, Sham Kakade, and Lin F Yang. Model-based reinforcement learning with a generative model is minimax optimal. In Conference Learning Theory, pages 67-83. PMLR, 2020.
[2] Mridul Agarwal, Bhargav Ganguly, and Vaneet Aggarwal. Communication efficient parallel reinforcement learning. In Uncertainty Artificial Intelligence, pages 247-256. PMLR, 2021.
[3] Shipra Agrawal and Randy Jia. Optimistic posterior sampling for reinforcement learning: worst-case regret bounds. Advances in Neural Information Processing Systems, 30, 2017.
[4] Aymen Al Marjani, Aurélien Garivier, and Alexandre Proutiere. Navigating to the best policy in markov decision processes. In Advances in Neural Information Processing Systems, pages 08852-25864, 2021.
[5] Aqeel Anwar and Arijit Raychowdhury. Multi-task federated reinforcement learning with adversaries. arXiv preprint arXiv:2/03.06477 2021.
[6] Mahmoud Assran, Joshua Romoff, Nicolas Ballas, Joelle Pineau, and Michael Rabbat. Gossip- based actor-learner architectures for deep reinforcement learning. Advances in Neural Infor- mation Processing Systems, 32, 2019.
[7] Peter Auer, Thomas Jaksch, and Ronald Ortner. Near-optimal regret bounds for reinforcement learning. Advances in Neural Information Processing Systems, 21, 2008.
[8] Peter Auer and Ronald Ortner. Logarithmic online regret bounds for undiscounted reinforce- ment learning. In Advances in Neural Information Processing Systems, pages 49-56. MIT Press, 2007.
[9] Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforcement learning. In International Conference on Machine Learning, pages 263-272. PMLR, 2017.
[10] Yu Bai, Tengyang Xie, Nan Jiang, and Yu-Xiang Wang. Provably efficient q-learning with low switching cost. Advances in Neural Information Processing Systems, 32, 2019.
[11] Soumya Banerjee, Samia Bouzefrane, and Amar Abane. Identity management with hybrid blockchain approach: A deliberate extension with federated-invent -nteees---eeiiforrmmmmn learning. In 2021 IEEE 22nd International Conference on High Performance Switching and Routing (HPSR), pages 1-6. IEEE, 2021.
[12] Ali Beikmohammadi, Sarit Khirirat, and Sindri Magnússon. Compressed federated reinforce- ment learning with a generative model. arXiv preprint arXiv:2404. 10635, 2024.
[13] Marc G Bellemare, Yavar Naddaf, Joel Veness, and Michael Bowling. The arcade learning environment: An evaluation platform for general agents. Journal of Artificial Intelligence Research, 47:253-279, 2013.
[14] Shulun Chen, Runlong Zhou, Zihan Zhang, Maryam Fazel, and Simon S Du. Sharp gap- dependent variance-aware regret bounds for tabular mdps. arXiv preprint 2566.0250..0 2025.
[15] Tianyi Chen, Kaiqing Zhang, Georgios B Giannakis, and Tamer Başar. Communication- efficient policy gradient methods for distributed reinforcement learning. IEEE Transactions on Control of Network Systems, 9(2)9977- 2021.

---

[16] Yiding Chen, Xuezhou Zhang, Kaiqing Zhang, Mengdi Wang, and Xiaojin Zhu. Byzantine- robust online and offline distributed reinforcement learning. In International Conference on Artificial Intelligence and Statistics, pages 3230-3269. PMLR, 2023.
[17] Ziyi Chen, Yi Zhou, Rong-Rong Chen, and Shaofeng Zou. Sample and communication- efficient decentralized actor-critic algorithms with finite-time analysis. In International Con- ference on Machine Learning, pages 3794-3833 3834. PMLR, 2022.
[18] Ziyi Chen, Yi Zhou, and Rongrong Chen. Multi-agent off- off-policy tde with near-optimal sample and communication complexity. In 202/ 55th Asilomar Conference Signals, Systems, and Computers, pages 504-508. IEEE, 2021.
[19] Paul Covington, Jay Adams, and Emre Sargin. Deep neural networks for youtube recom- mendations. In Proceedings of the 10th ACM Conference on Recommender Systems, pages 191-198, 2016.
[20] Christoph Dann, Lihong Li, Wei Wei, and Emma Brunskill. Policy certificates: Towards accountable reinforcement learning. In International Conference on Machine Learning, pages 1507-1516. PMLR, 2019.
[21] 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, pages 1626-1635. PMLR, 2019.
[22] Thinh T Doan, Siva Theja Maguluri, and Justin Romberg. Finite-time performance of dis- tributed temporal-differene learning with linear function approximation. SIAM Journal on Mathematics of Data Science, 3(1):298-33))) 2021.
[23] Simon S Du, Jianshu Chen, Lihong Li, Lin Xiao, and Dengyong Zhou. Stochastic variance reduction methods for policy evaluation. In International Conference on Machine Learning, pages 1049-1058 PMLR, 2017.
[24] Abhimanyu Dubey and Alex Pentland. Provably efficient cooperative multi-agent reinforce- ment learning with function approximation. arXiv preprint 1rXiv:2103.04972, 2021.
[25] Lasse Espeholt, Hubert Soyer, Remi Munos, Karen Simonyan, Vlad Mnih, Tom Ward, Yotam Doron, Vlad Firoiu, Tim Harley, lain Dunning, et al. Impala: Scalable distributed deep-rl with importance weighted actor-learner architectures. In International Conference on Machine Learning, pages 1407-1416. PMLR, 2018.
[26] 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:100771021, 2021.
[27] Flint Xiaofeng Fan, Yining Ma, Zhongxiang Dai, Cheston Tan, and Bryan Kian Hsiang Low. Fedhql: Federated heterogeneous q-learning In Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems, pages 2810-281 211022812,20 2023.
[28] Swetha Ganesh, Jiayu Chen, Gugan Thoppe, and Vaneet Aggarwal. Global convergence guaran- tees for federated policy gradient methods with adversaries. arXiv preprint 29X9042403.09940, 2024.
[29] Zijun Gao, Yanjun Han, Zhimei Ren, and Zhengqing Zhou. Batched multi-arma bandits problem. Advances in Neural Information Processing Systems, 32, 2019.
[30] Wei Gong, Linxiao Cao, Yifei Zhu, Fang Zuo, Xin He, and Haoquan Zhou. Federated inverse reinforcement learning for smart icus with differential privacy. IEEE Internet of Things Journal, 10221):1917--19124 2023.
[31] Robert M Gower, Mark Schmidt, Francis Bach, and Peter Richtárik. Variance-reduced methods for machine learning. Proceedings of the IEEE, 1861119966-1111 1983, 2020.
[32] Shixiang Gu, Ethan Holly, Timothy Lillicrap, and Sergey Levine. Deep reinforcement learning for robotic manipulation with asynchronous off-policy updates. In 2017 IEEE International Conference on Robotics and Automation (ICRA), pages 3389-3396. IEEE, 2017.
12

---

[33] Zhaohan Guo and Emma Brunskill. Concurrent pac rl. In Proceedings of AAAI Conference on Artificial Intelligence, volume 29, pages 2622-2622222 2015.
[34] Jiafan He, Dongruo Zhou, and Quanquan Gu. Logarithmic regret for reinforcement learning with linear function approximation. In International Conference Machine Learning, pages 4171-4180. PMLR, 2021.
[35] Hao-Lun Hsu, Weixin Wang, Miroslav Pajic. and Pan Xu. Randomized exploration in cooper- ative multi aulti-agent reinforcement learning. arXiv preprint arXiv:2404.10728, 2024.
[36] Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 11:1563-1000, 2010.
[37] Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael I Jordan. Is q-learning provably efficient? Advances in Neural Information Processing Systems, 31, 2018.
[38] Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference Learning Theory, pages 2137-2143. PMLR, 2020.
[39] 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, pages 18-37. PMLR, 2022.
[40] Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. Advances in Neural Information Processing Systems, 26, 2013.
[41] Anders Jonsson, Emilie Kaufmann, Pierre Ménard, Omar Darwiche Domingues, Edouard Leurent, and Michal Valko. Planning in markov decision processes with gap-dependent sample complexity. Advances in Neural Information Processing Systems, pages 1253-1263, 2020.
[42] Sham Kakade, Mengdi Wang, and Lin Yang. Variance reduction methods for sublinear reinforcement learning. arXiv preprint arXiv: 1802.09/84 2018.
[43] Koulik Khamaru, Ashwin Pananjady, Feng Ruan, Martin J Wainwright, and Michael Jordan. Is temporal difference learning optimal? an instance-dependent analysis. SIAM Journal on Mathematics of Data Science, 344::013311040 2021.
[44] Sajad Khodadadian, Pranay Sharma, Gauri Joshi, and Siva Theja Maguluri. Federated rein- forcement learning: Linear speedup under markovian sampling. International Conference on Machine Learning, pages 10997-11057. PMLR, 2022.
[45] Jens Kober, J Andrew Bagnell, and Jan Peters. Reinforcement learning in robotics: A survey. The International Journal of Robotics Research, 32(1
2013.
[46] Safwan Labbi, Daniil Tiapkin, Lorenzo Mancini, Paul Mangold, and Fric Moulines. Federated ucbvi: Communication-cffiiii federated regret minimization with heterogencous agents. In The 28th International Conference on Artificial Intelligence and Statistics, 2025.
[47] Guangchen Lan, Dong-Jun Han, Abolfazl Hashemi, Vaneet Aggarwal, and Christopher G Brin- ton. Asynchronous federated reinforcement learning with policy gradient updates: Algorithm design and convergence analysis. arXiv preprint arXiv:2404. 08003, 2024.
[48] Guangchen Lan, Han Wang, James Anderson, Christopher Brinton, and Vaneet Aggarwal. Improved communication efficiency federated natural policy gradient via admm-based gradient updates. arXiv preprint arXiv:2310. 19807, 2023.
[49] Gen Li, Changxiao Cai, Yuxin Chen, Yuting Wei, and Yuejic Chi. Is q-learning minimax optimal? a tight sample complexity analysis. Operations Research, 72(1):222-25) 2024.
[50] Gen Li, Laixi Shi, Yuxin Chen, and Yuejie Chi. Breaking the sample complexity barrier to regret-optimal model-free reinforcement learning. Information and Inference: A Journal of the IMA, 12(2):969-1000 2023.
13

---

[51] Gen Li, Yuting Wei, Yuejie Chi, Yuantao Gu, and Yuxin Chen. Sample complexity of asynchronous q-learning: Sharper analysis and variance reduction. Advances in Neural Information Processing Systems, 33:7031-7043, 2020.
[52] Tian Li, Anit Kumar Sahu, Ameet Talwalkar, and Virginia Smith. Federated learning: Chal- lenges, methods, and future directions. IEEE signal processing magazine, 37(3):50-60, 2020.
[53] Rui Liu and Alex Olshevsky. Distributed td (0) with almost no communication. IEEE Control Systems Letters, 2023.
[54) Shicheng Liu and Minghui Zhu. Distributed inverse constrained reinforcement learning for multi-agent systems. Advances in Neural Information Processing Systems, 35:33444-333555 2022.
[55] Shicheng Liu and Minghui Zhu. Meta inverse constrained reinforcement learning: Convergence guarantee and generalization analysis. In The Twelfth International Conference on Learning Representations, 2023.
[56] Shicheng Liu and Minghui Zhu. Learning multi aggent behaviors from distributed and streaming demonstrations, Advances in Neural Information Processing Systems, 36, 2024.
[57] Shicheng Liu and Minghui Zhu. In-trajectory inverse reinforcement learning: Learn incre- mentally before an ongoing trajectory terminates. The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2025.
[58] Shicheng Liu and Minghui Zhu. Utility: Utilizing explainable reinforcement learning to improve reinforcement learning. In The Thirteenth International Conference on Learning Representationss 2025.
[59] AA Marjani and Alexandre Proutiere. Best policy identification in discounted mdps: Problem- specific sample complexity. arXiv preprint arXiv:2009.1344 13405, 2020.
[60] Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communicaton--effcceenn learning of deep networks from decentralized data. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, volume 54, pages 1273-1282. PMLR, 2017.
[61] Pierre Ménard, Omar Darwiche Domingues, Xuedong Shang, and Michal Valko. Ucb mo- mentum q-learning: Correcting the bias without forgetting. In International Conference on Machine Learning, pages 7609-7618. PMLR, 2021.
[62] Yifei Min, Jiafan He, Tianhao Wang, and Quanquan Gu. Cooperative multi-agent reinforcement learning: Asynchronous communication and linear function approximation. In International Conference on Machine Learning, pages 24785 -2811. PMLR, 2023.
[63] Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforce- ment learning. In International Conference on Machine Learning, pages 1928-1937. PMLR, 2016.
[64] Lam M Nguyen, Jie Liu, Katya Scheinberg, and Martin Takáč. Sarah: A novel method for machine learning problems using stochastic recursive gradient. In International Conference on Machine Learning, pages 2613-2621. PMLR, 2017.
[65] Thanh Nguyen-Tange Ming Yin, Sunil Gupta, Svetha Venkatesh, and Raman Arora. On instance-dependent bounds for offline reinforcement learning with linear function approxi- mation. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 9310-9318,
2023.
[66] Jungseul Ok, Alexandre Proutiere, and Damianos Tranos. Exploration in structured reinforce- ment learning. Advances in Neural Information Processing Systems, 31, 2018
[67] Vianney Perchet, Philippe Rigollet, Sylvain Chassang, and Erik Snowberg. Batched bandit problems. The Annals of Statistics, 44(2):660- 681, 2016.
14

---

[68] Dan Qiao, Ming Yin, Ming Min, and Xu-Xiang Wang. Sample-efficient reinforcement learning with loglog (t) switching cost. In International Conference on Machine Learning, pages 18031-18061. PMLR, 2022.
[69] Han Shen, Kaiqing Zhang, Mingyi Hong, and Tianyi Chen. Towards understanding asyn- chronous advantage actor-critic: Convergence and linear speedup. IEEE Transactions Signal Processing, 2023.
[70] Laixi Shi, Gen Li, Yuting Wei, Yuxin Chen, and Yuejie Chi. Pessimistic q-learning for offline reinforcement learning: Towards optimal sample complexity. In International Conference on Machine Learning, pages -9965-20025. PMLR, 2022.
[71] Aaron Sidford, Mengdi Wang. Xian Wu, Lin Yang, and Yinyu Ye. Near-optimal time and sample complexities for solving markov decision processes with generative model. Advances in Neural Information Processing Systems, 31, 2018.
[72] Aaron Sidford, Mengdi Wang, Xian Wu, and Yinyu Ye. Variance reduced value iteration and faster algorithms for solving markov decision processes. Naval Research Logistics (NRL), 70(5):423-444 442, 2023.
[73] David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schritwweser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanc- tot, et Mastering the game of go with deep neural networks and tree search. Nature, 529(7587):484 2016.
[74] David Silver, Thomas Hubert, Julian Schrittwieser, loannis Antonoglou, Matthew Lai, Arthur Guez, Marc Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, et al. Mastering chess and shogi by self-play with general reinforcement learning algorithm. arXiv preprint arXiv:1712.01815, 2017.
[75] David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Marc Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, et al. general reinforcement learning algorithm that masters chess, shogi, and go through self-play. Science, 362(6419): 1144,14, 2018.
[76] Max Simchowitz and Kevin G Jamieson. Non-asymptotic gap-dependent regret bounds for tabular mdps. In Advances in Neural Information Processing Systems, 2019.
[77] Jun Sun, Gang Wang, Georgios Giannakis, Qinmin Yang, and Zaiyue Yang. Finite-time analysis of decentralized temporal-differenc learning with linear function approximation. In International Conference on Artificial Intelligence and Statistics, pages 4485-4495. PMLR, 2020.
[78] R Sutton and A Barto. Reinforcement Learning: An Introduction. MIT Press, 2018.
[79] Ambuj Tewari and Peter Bartlett. Optimistic linear programming gives logarithmic regret for irreducible mdps. In Advances in Neural Information Processing Systems, pages 1505-1512, 2008.
[80] Andrea Tirinzoni, Aymen Al Marjani, and Emilie Kaufmann. Near instance-optimal pac reinforcement learning for deterministic mdps. Advances in Neural Information Processing Systems, pages 8785-8798, 2022.
[81] Andrea Tirinzoni, Aymen Al-Marjani, and Emilie Kaufmann. Optimistic pac reinforcement learning: the instance-dependent view. In International Conference on Algorithmic Learning Theory, pages 1460-1480. PMLR, 2023.
[82] Oriol Vinyals, Igor Babuschkin, Wojeiech M Czarnecki, Michaël Mathieu, Andrew Dudzik, Junyoung Chung. David H Choi, Richard Powell, Timo Ewalds, Petko Georgiev, et al. Grand- master level starcraft ii using multi-agent reinforcement learning. Nature, 555(7782):300- 354, 2019.
15

---

[83] Andrew Wagenmaker and Kevin G Jamieson. Instance-dependen near-optinng near-optimal policy identifi- cation linear mdps via online experiment design. Advances Neural Information Processing Systems, 35:5968- 5981, 2022.
[84] Andrew J Wagenmaker, Yifang Chen, Max Simchowitz, Simon Du and Kevin Jamieson. First-order regret in reinforcement learning with linear function approximation: A robust estimation approach. In International Conference on Machine Learning, pages 22384-22429. PMLR, 2022.
[85] Andrew J Wagenmaker, Max Simchowitz, and Kevin Jamieson. Beyond no regret: Instance- dependent pac reinforcement learning. In Conference on Learning Theory, pages 358-418 PMLR, 2022.
[86] 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), pages 4897-4902. IEEE, 2020.
[87] Hoi-To Wai, Mingyi Hong, Zhuoran Yang, Zhaoran Wang, and Kexin Tang. Variance reduced policy evaluation with smooth function approximation. Advances in Neural Information Processing Systems, 32, 2019.
[88] Martin J Wainwright. Variance-reduced q-learning is minimax optimal. arXiv preprint Stti::1906.049999 2019.
[89] 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 Information Processing Systems, 33:13762-13772. 2020.
[90] Tianhao Wang, Dongruo Zhou, and Quanquan Gu. Provably efficient reinforcement learn- ing with linear function approximation under adaptivity constraints. Advances in Neural Information Processing Systems,
2021.
[91] Xinqi Wang, Qiwen Cui, and Simon $ Du. On gap-dependent bounds for offline reinforcement learning. Advances in Neural Information Processing Systems, 35: 15:14865-14877, 2022.
[92] 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, pages 37 37157- 37216, 2023.
[93] Jiin Woo, Laixi Shi, Gauri Joshi, and Yuejic Chi. Federated offline reinforcement learning: Col- laborative dingle-polic coverage suffices. In International Conference on Machine Learning, pages
2024.
[94] Zhaoxian Wu, Han Shen, Tianyi Chen, and Qing Ling. Byzantine-resilient decentralized policy evaluation with linear function approximation. IEEE Transactions on Signal Processing, 69:3839-3853, 2021.
[95] Haike Xu, Tengyu Ma, and Simon Du. Fine-grained gap-dependent bounds for tabular mdps via adaptive multi-step bootstrap. In Conference on Learning Theory, pages 4438-4472. PMLR, 2021.
[96] Tengyu Xu, Zhe Wang, Yi Zhou, and Yingbin Liang. Reanalysis of variance reduced temporal difference learning. In International Conference on Learning Representations, 2020.
[97] Yuling Yan, Gen Li, Yuxin Chen, and Jianqing Fan. The efficacy of pessimism in asynchronous q-learning. IEEE Transactions on Information Theory, 2023.
[98] Kunhe Yang, Lin Yang, and Simon Du. Q-learning with logarithmic regret. In International Conference on Artificial Intelligence and Statistics, pages 1576-1584, PMLR, 2021.
[99] Tong Yang, Shicong Cen, Yuting Wei, Yuxin Chen, and Yuejie Chi. Federated natural policy gradient methods for multi-task reinforcement learning. arXiv preprint arXiv:2311.0022 2023.
16

---

[100] Ming Yin. Yu Bai, and Yu-Xiang Wang. Near-optimal offline reinforcement learning via double variance reduction. In Advances Neural Information Processing Systems, pages 7677-7688, 2021.
[101] Ekim Yurtsever, Jacob Lambert, Alexander Carballo, and Kazuya Takeda. A survey of autonomous driving: Common practices and emerging technologies. IEEE Access, 8:58443- 58469, 2020.
[102] Andrea Zanette and Emma Brunskill. Tighter problem-dependent regret bounds in reinforce- ment learning without domain knowledge using value function bounds. In International Conference on Machine Learning, pages 7304-7312. PMLR, 2019.
[103] Sihan Zeng, Thinh T Doan, and Justin Romberg. Finite-time analysis of decentralized stochastic approximation with applications multi-agent and multi-task learning. In 202/ 60th IEEE Conference on Decision and Control (CDC), pages 2641-2646. IEEE, 2021.
[104] Chenyu Zhang, Han Wang, Aritra Mitra, and James Anderson. Finite-time analysis of on- policy heterogeneous federated reinforcement learning. arXiv preprint arXiv:2401.1527 2024.
[105] Haochen Zhang, Zhong Zheng, and Lingzhou Xue. Gap-dependent bounds for federated SqS-learning. In Forty-second International Conference on Machine Learning. 2025.
[106] Haochen Zhang, Zhong Zheng, and Lingzhou Xue. Q-learning with fine-grained gap-dependent regret. arXiv preprint arXiv:2510.06647, 2025.
[107] Zihan Zhang, Yuxin Chen, Jason D Lee, and Simon S Du. Settling the sample complexity of online reinforcement learning. In Conference Learning Theory, pages 5213-5219, PMLR, 2024.
[108] Zihan Zhang, Xiangyang Ji, and Simon Du. Is reinforcement learning more difficult than bandits? near-optimal algorithm escaping the curse of horizon. In Conference Learning Theory, pages 4528 4531. PMLR, 2021.
[109] Zihan Zhang, Xiangyang Ji, and Simon Du. Horizon-free reinforcement learning in polynomial time: the power of stationary policies. Conference on Learning Theory, pages 3858-3904. PMLR, 2022.
[110] 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.
[111] Zihan Zhang, Yuan Zhou, and Xiangyang Ji. Almost optimal model-free reinforcement learning via aederance-advantage decomposition. Advances Neural Information Processing Systems, 23:15198-1520 2020.
[112] Fangyuan Zhao, Xuebin Ren, Shusen Yang. Peng Zhao, Rui Zhang, and Xinxin Xu. Federated multi-objective reinforcement learning. Information Sciences, 14::1118332 2023.
[113] Zhong Zheng, Fengyu Gao, Lingzhou Xue, and Jing Yang. Federated q-learning: Linear regret speedup with low communication cost. In The Twelfth International Conference Learning Representations, 2024.
[114] Zhong Zheng, Haochen Zhang, and Lingzhou Xue. Federated q-learning with reference- advantage decomposition: Almost optimal regret and logarithmic communication cost, The Thirteenth International Conference on Learning Representations, 2025.
[115] Zhong Zheng, Haochen Zhang, and Lingzhou Xue. Gap-dependent bounds for q-learning using reference-advantagge decomposition. In The Thirteenth International Conference on Learning Representations, 2025.
[116] Runlong Zhou, Zhang Zihan, and Simon Shaolei Du. Sharp variance-dependent bounds in reinforcement learning: Best of both worlds stochastic and deterministic environments, In International Conference Machine Learning, pages 42878 1788-4914. PMLR, 2023.
17

---

Organization of the appendix. Appendix A reviews related works. Appendix B presents the results of our numerical experiments, demonstrating the best regret performance and showing the log T-ype switching/commuiicttoo cost. Appendix C analyzes our technical novelty that leads to the regret improvement. Appendix provides graphical illustrations and two notation tables for our algorithms. Appendix E and Appendix F include some useful theorems and lemmas. Appendix G proves some probability events and Appendix explores the properties of estimated value functions. Appendix I contains the proof of the worst-case regret bounds (Theorem 4.1 and Theorem 4.3). Appendix J contains the proof of the worst-case and Theorem 4.4). Appendix K provides the proof of the gap-dependent regret bounds (Theorem 4.5 and Theorem 4.8). Appendix L presents the proof of the gap-dependent switchig/coommuication cost bounds (Theorem 4.7 and Theorem 4.9).
cost bounds (Theorem 4.2
A Related Work
On-Policy RL for Finite-Horizon Tabular MDPs with Worst-Case Regret. There are mainly two types of algorithms for reinforcement learning: model-basee and model-free learning. Model-based algorithms learn a model from past experience and make decisions based on this model, while model-free algorithms only maintain group of value functions and take the induced optimal actions. Due to these differences, model-free algorithms are usually more space-efficient and time-efficient compared with model-based algorithms. However, model-based algorithms may achieve better learning performance by leveraging the learned model.
Next, we discuss the literature on model-based and model-free algorithms for mnite-horizon tabular MDPs with worst-case regret. [1, 7, 9, 20, 42, 102, 107, 108, 1 16] focus on model-based algorithms. Notably, [107] provide an algorithm that achieves a regret of Ó (min (VSS AAHT, T)), which matches the information-theoree
lower bound. [37, 50, 61, 98, 111] focus on model-free algorithms. Three of them [50. 61, 111] achieve the near-optimal regret of Ó Ö(VSAH²T).
Suboptimality Gap. When there is a strictly positive suboptimalityy gap, is possible to achieve logarithmic regret bounds. In RL, carlier work obtains asymptotic logarithmic regret bounds [8, 79]. Recently, non-asymptotic logarithmic regret bounds are obtained [34, 36, 66, 76). Specifically, [36] develops model-based algorithm, and their bound depends the policy gap instead of the action gap studied in this paper. [66] derives problem-specific logarithmic type lower bounds for both structured and unstructured MDPs. [76] extends the model-based algorithm proposed by [102] and obtains logarithmic regret bounds. More recently. [14] further improves model-based gap-dependent results. Logarithmic regret bounds are also established in the linear function approximation setting [34], and [65] provides gap-dependent guarantees for offline RL with linear function approximation.
Specifically, for model-free algorithms, [98] shows that the optimistic Q-learning algorithm in [37] enjoys a logarithmic regret O( (''',,, which is subsequently refined by [95]. In their work, [95] introduces the Adaptive Multi-step Bootstrap (AMB) algorithm. [115] further improves the logarithmic regret bound by leveraging the analysis of the UCB-Advantage algorithm [111] and the Seeeeeeedd--ddaaaaeeeee algorithm [50]. [106] provides the first fine- finengrined, gap-dependent regret upper bound for a UCB-based algorithm, specifically UCB-Hoeffding further establishes the first gap-dependent bounds for both regret and communication cost.
In the federated setting, [105]
Several other studies also investigate gap-dependent sample complexity bounds [4, 41, 59, 80, 81, 83, 85, 91].
Variance Reduction RL. The reference-advantagg decomposition used [50] and [111] is a technique of variance reduction that is originally proposed for finite-sum stochastic optimization [31, 40, 64]. Later, model-free RL algorithms also use variance reduction to improve sample efficiency. For example, it is used in learning with generative models [71, 72, 88), policy evaluation [23, 43, 87, 96), offline RI. (70, 100), and Q-learning (50, 51, 97, 111].
RL with Low Switching Costs and Batched RL, Research in RL with low switching costs aims to minimize the number of policy switches while maintaining comparable regret bounds to fully adaptive counterparts, and it applies to federated RL. In batched RL [29, 67]. the agent sets the number of batches and the length of each batch upfront, implementing an unchanged policy in a batch and aiming for fewer batches and lower regret. [10] first introduces the problem of RL with low switching cost and proposes Q learning algorithm with lazy updates, achieving Ō(H SA log T') switching
18

---

cost. This work is advanced by [111], which improves the regret upper bound and the switching cost simultaneously. Additionally, [90] studies RL under the adaptivity constraint. Recently, [68] proposes model-based algorithm with Óllog log 7) switching cost. [0] proposes a batched RL. algorithm that is well-suited for the federated setting.
Multi-Agent RL (MARL) with Event-Triggered Communications. We review few recent works on on-policy MARL with linear function approximations. [24] introduces Coop-LSVI for cooperative MARL. [62] proposes an asynchronous version of LSVI-UCB that originates from [38], matching the same regret bound with improved communication complexity compared with [24]. [35] develops two algorithms that incorporate randomized exploration, achieving the same regret and communication complexity as [62]. [24, 35, 62] employ event- wvint-triggered communication conditions based on determinants of certain quantities. Different from our federated algorithm, during the synchronization in [24] and [62], local agents share original rewards or trajectories with the server. On the other hand, [35] reduces communication cost by sharing compressed statistics in the non-tabular setting with linear function approximation.
Federated and Distributed RL. Existing literature on federated and distributed RL algorithms
highlights various aspects. For value-based algorithms, [33], [92], and [113] focus on linear speedup. [2] proposes parallel RL algorithm with low communication cost. [92] and [93] discuss the improved covering power of heterogeneity. [16] and [94] work on robustness. Particularly, [16] proposes algorithms both offline and online settings, obtaining near-optimal sample complexities and achieving superior robustness guarantees. In addition, several works investigate value-based algorithms such Q-learning in different settings, including [5, 12, 27, 39, 44, 92, 93, 99, 104, 112]. The convergence of decentralized temporal difference algorithms is analyzed by [18, 21, 22, 53, 77, 86, 89, 103].
Some other works focus on policy gradient-based algorithms. Communication--ffiiienn policy gradient algorithms are studied by [15] and [26]. [48] further reduces the communication complexity and also demonstrates a linear speedup in the synchronous setting. Optimal sample complexity for global convergence in federated RL, even in the presence of adversaries, is studied in [28]. [47] proposes an algorithm to address the challenge of lagged policies in asynchronous settings.
The convergence of distributed actor-critic algorithms is analyzed by [17, 69]. Federated actor-learner architectures are explored by [6, 25, 63). Distributed inverse reinforcement learning is examined by [11, 30, 54, 55, 56, 57, 58).
B Numerical Experiments
In this section, we present experiments conducted in a synthetic environment to demonstrate the following two conclusions:
When M 1, D-EarlySetled-LLowCCC achieves better regret compared with all other single-agent model-free algorithms: UCB- BCCB-Hoefdiin and BCB-Bernstein [37], UCB2- Hoeffding and UCB2B [10], UCB-Advantage [111] and --EarlySettlcd-Advaaatee [50], while maintaining logarithmic switching cost.
FedQ Serel---aySSttted-eeeeee LowClsst achieves the best regret performance compared with other federated model-free algorithms, including FedQ-Hoeffding and BedtQ-Bersttein[11 [3] and FedQ-Advantage [1 [1]4], while also maintaining logarithmic communication cost.
To evaluate the proposed algorithms, we simulate a synthetic tabular episodic Markov Decision Process. Specifically, we consider two cases with (H, S, A) (5, 3, 2) and (7, 10, 5). The reward (n a) for each (s, a, fi) is generated independently and uniformly at random from [0, 1]. Pn generated on the S-dimensional simplex independently and uniformly at random for (s, a, h). Then we will discuss the experiment results for each conclusion separately.
B.1 Comparison of Single-Agent RL Algorithms
Under the given MDP, we set M = 1 and generate 3 10 episodes for (H,S, A) (5,3, and 2 o0t episodes for (H, S, A) (7, 10,5). 5). For each episode, we randomly choose the initial state
19

---

uniformly from the S states For the other six single-agent algorithms, we use their hyperparameter settings based on the publicly available code" in [115]. For EarlySettled-Loww algorithm. we similarly set 1, the hyper-parameter сı / in the bonus b, c in the cumulative bonus
R22 Ph % = 1 in the bonus by,, and B = 0.05.
To show error bars, we collect 10 sample paths for all algorithms under the same MDP environment and show the relationship between Regret(")) log(T + 1) and the total number of episodes for each agent T/ in Figure For both panels, the solid line represents the median of the 10 sample paths, while the shaded area shows the 10th and 90th percentiles.
250
14000
Le0 Stalle
LCB HoaetSingg
300
12000
LCD Baritsh
LCB co--dcartage
Early
Regiet7/MooTM4 33
10000
Regret RegeeTingitte
200
A000
100
50-
2000
50000
200000 Total number opisodes TM
100000
150000
250000
300000
0.00
0.25
0.50
0.75
1.00
1.25
1.50
1.75
2.00
Total number opisodes TIN
1e6
(a) Regret results for (H, S. A) (5, (5,3,2) 2)
(b) Regret results for (H, S, A) (7, 10,
Figure I: Numerical comparison of regrets for single-agen. aggett model-free algorithms
From the two figures, we observe that when M = 1, our Q-EarlySettled-Loww algorithm enjoy the best regret compared with the other six single-agent model-free algorithms. We also note that the red curves for the Q-EartySSetled-LLwwCoo algorithm approach horizontal lines as the total number of episodes T/ becomes sufficiently large. Since the y-axis is (Tgret(T)) log(T) (T/L) H + 1), this suggests that the regret grows logarithmically with T, which matches gap-dependent regret bound result in Theorem 4.5. also show the logarithmic switching cost results the following Figure 2.
1000
Pelci Switching Cost logitw
800
Policy Switchng Coplleghh
40
20-
200
EarlySettied
D-Early
50000
100000
150000
200000
250000
300000
0.00
0.25
0.50
0.75
1.00
1.25
1.50
1.75
2.00
185
Switching cost for (H, A) (5.
(b) Switching cost for (H, S,
10,
Figure 2: Switching cost results for Q-EartySetlled-Loooost when M =
From Figure 2, note that the red curves for Q-EaarlySettted-LowCC algorithm also approach horizontal lines as the total number of episodes T/ H becomes sufficiently large. This suggests that the switching cost grows logarithmically with T, which matches our logarithmic switching cost bound result in Theorem 4.2 and Theorem 4.7.
All the experiments in this subsection cores. Each replication is limited to single core and 8GB RAM. The total execution time about hours. code numerical experiments is included in the supplementary materials along with the submission. maattrralll
with Intel Xeon E5 E5-2650v4 (2.2GHz) and 100
20

---

B.2 Comparison of FRL Algorithms
Under the given MDP, we set M 10 and generate 3 * 10 episodes for (H, S, A) = (5,3, 2) and 10 episodes for (H S, A) (7, 10,5). For each episode, we randomly choose the initial state uniformly from the S states. For the other three federated model-free algorithms, FedQ- Hoeffding, Bed@-Bernstein, and FedQ-Advantage, we use their hyperparameter settings based on publicly available code" in [114]. For the reeQ--ErryySettle--LooCo algorithm, we use the same hyperparameter setting as specified in Appendix B.1.
To show error bars, we also collect 10 sample paths for all algorithms under the same MDP environ- ment and show the relationship between Regret(T)/ log( H + 1) and the total number episodes for each agent T/ H in Figure 3. For both panels, the solid line represents the median of the 10 sample paths, while the shaded area shows the 10th and 90th percentiles.
hoeflding Sunstein Advantage
250
19000
300
10000
EarlySettied
250
0000
200
6000
50000
100000
150000
200000
250000
300000
1.75
2.00
Regret results for (H, A) 3,
Regret results for (H, A) (7, 10,
Figure 3: Numerical comparison of regrets for federated model-free algorithms
From the two figures, we observe that our proposed Fed(--EatySeetled-Loww LowCost algorithm enjoy the best regret compared with the other three federated model-free algorithms. We also note that the red curves for the FedQ-Earlye Sares--EeaaSSeee--LLoooo Lowtls algorithm approach horizontal lines as the total number of episodes T/H becomes sufficiently large. This suggests that the regret grows logarithmically with T, which matches our gap-dependent regret bound result Theorem 4.8.
120
Number of communtation counds Khogr7M
Number of communcation rounds Kibaatt
100
800
800
40
400
200
FedO EarlySetted
FeaD: EarlySettied LowCost
50000
150000
200000 250000
300000
0.00
0.25
0.50
0.75
1.00
1.25
1.50
1.75
2:00
Total
1u6
(a) Communication cost for (I,, A) (5,3.2)
Communication cost for (JT, S, (7. 10,
Figure 4: Number of communication rounds for
'All the experiments in this subsection
with Intel Xeon E5 E5-2650v4 (2.2GHz) and 100
cores. Each replication is limited to five cores and 15GB RAM. The total execution time is about hours. The code for the numerical experiments is included in the supplementary materials along with the submission. _mttiiiallt
21

---

From Figure 4, we find that the number of communication rounds curves for the BedQ-EarlySettlee LowCost algorithm approach horizontal lines as the total number of episodes T/H becomes suffi- ciently large. This suggests that the number of communication rounds grows logarithmically with T, which matches our logarithmic gap-dependent communication cost bound result in Theorem 4.4 and Theorem 4.9.
C Technical Novelty in Depth
In this section, we highlight our technical novelty for proving the worst-case regrets for both Q-EarlySetleddLLwwCC and SadQQ-ErlyySttted-oowCCoo
where overcome the challenge of simultancous non-adaptiveness by using the surrogate reference function.
We prove the worst-case regret bounds in Theorem 4.1 and Theorem 4.3 by relating the regret the estimation error of the optimal Q Q-QQQnnan functions that takes the form
Σ (5% k..m -4 (. A:j.m
It is common in the literature to bound the summation by recursions on in model-free algorithms
[50, 98, 111, 113]. In more detail, for each individual error (Qh: Q2) k.j.m R.j.m) ), by the update rule in Equation (7), it can be upper bounded by (QT. (i)( k..m on the dicerence-avvnttaee Appendix shows that with high probability, (Q) (5 ,4
(sh
H. an k.d.m). Furthermore, based update given in Equation (11) and Equation (15), Equation (77) in R.
k.j. k.J.m
I Go. where
N Σ
9o
N On
VRAA" 1" mm
( hhi (5 + p4
""
R
P
k.mm dimm Vh+t + CB- sy
at
Here, k" represents the round index that the n-th visit to k.j. the cumulative weight for the n-th visit to this state-action-ster triple under our delayed-policy- No _N -h kjj. h) happens. 1hn denotes
switching scheme (see Equation (19) in Appendix for the definition), which approximates r/n (the exact weight in high burn-in cost algorithms requiring frequent policy updates [37, 50]). Cg collects some constants and the cumulative bonuses. All three notations hide their dependency on (k, m, h). We start from the decomposition of Go. following the design in [50] for (-FarlySemled-AAAaniie with frequent policy switching, and then explain the challenges of adnaaiativeeeess therein and our solution of surrogate reference function.
Decomposition. We use V,R. R to denote the settled reference function. By applying the inequality V RRA
A+1 h+1 - 1 kRR,+ which follows directly from the monotonically non-increasing h+1
V.
property of R.k guaranteed by the reference function settling rule in line 12 of Algorithm 1, Go can be further upper bounded by the summation CB and the following terms:
9 =
Th
(Vitt - Vitta) (8h "" "mmmm """,
N
G2
Σ
7n
No
kn pm. Persim
ot Caammatiiiim (o.mm...smm))) (.ssi..)) in) (Vi+z Vh+1 V.R.K-))
N
N
G3
Th
N
+1
(. ( ('
VRKK+ K11
h+1 (5
( ((
:=:=1
N
N
(vR.K+1 Af (s h+11 (841
kisi aha.m
baa. J.
VRRK+1) K+
h+1
1=1
This decomposition follows the structure of the reference-advantage decomposition, where G1 reflects the V-value function estimation error, G2 and G4 reflect the empirical estimation error for the settled
22

---

advantage function and reference function respectively, and G3 reflects the reference settling error. Thus, the estimation eπror j.m (Q ( k.j.m k.J. can be upper bounded by the sum of five corresponding summations with regard to CB, 91, G2, 93, 94.
.up
Challenges: Simultancous Non- Mon-Adaptiseness. However, the summations involving G2 and G4 cannot be directly bounded using standard concentration inequalities. This limitation arises from the
{fin k } and the settled reference function vR.K+1 at the h+1
non-adaptive nature both the weights
next steps of historical visits to (s% 0% k.J.m h).
&..m
The weights (7i exhibit non-adaptiveness due our special aggregation scheme used in Case 2 of the estimated 22-function updates (Equation (7)), which assigns identical weights to all visits within given round. Each weight depends the total number of visits to the corresponding state- action-step triple in that round, a quantity that is unknown during visitation due to our event-triggered termination condition specified in Equation (3). This uncertainty results in the non-adaptiveness of the weights. The non-adaptiveness of h++1 is because the reference settling depends on all the historical information in the learning process (see line 12 in Algorithm for the reference function's 's update rule).
[113] addresses the non-adaptiveness of the weights through round-wise approximations, and [50] tackles the non-adaptiveness related the settled reference function via the empirical process.
However, neither approach simultaneously resolves both forms of non-adaptiveness, and their direct combination presents significant technical challenges. The empirical process employed in [50] introduces an additional logarithmic factor of T' in the error bound when constructing e-nets to cover the function space induced by pR,K+1
h++1
Surrogate Reference Functions. To combine the round-based design (with equal weight assignments in each round) and the LCB technique (used in the reference-advanttee decompo- sition) for simultaneous low burn-in costs and logarithmic wwiiching/oommunicatinnn costs, we adapt the surrogate reference function technique from [115] [115]-orgiinally developed for gap-dependent analysis- and successfully incorporate it into our worst-case regret framework. There are two benefits of this adaptation: (i) It resolves the fundamental challenge of simultaneous non -daptieats in the learning process. (ii) By replacing the empirical process technique from [50], it eliminates the additional logarithmic factor in the error bound, yielding tighter regret guarantees.
Our Solution:
The surrogate reference function Vi in our framework is defined as:
R. (s) max V% (s), min { V% 8,, vr (s) Mss
It naturally adapts to the learning process. In addition, building on the optimistic property demon- strated in Lemma H. we can show that
VR min (x) ( +
with high probability. Thus, it maintains the same monotonically non-increasing property as the reference function V)R,((s) and coincides with the settled reference function V, K2 once the reference function is settled (see line 12 in Algorithm 1 for the update rule of reference functions). By applying the inequality VAA"1 R. < VVA" V.R.." Go can be upper bounded by the summation of CB. 91, G2, Gs, G4, where all the RR,++ are replaced by the surrogate reference function 17
k+1
In the new decomposition, the summation over CB is well-controleed in Lemma I.1, following similar approach to [50, Appendix E.2]. The summation over Gi can be bounded by
Σ k.j.m
(0h - 1i+1)
j.j.m k.j.my (8 0
exp
F
and an additional constant term as shown in Equation (82) of Appendix I, establishing the error recursion for step ht This step relies on a double-sum rearrangement, a standard technique in model- free RL analysis [37, 50, 113]. The summation for G3 can be bounded in the term R3,3 of Lemma I.3, using the technique from [50, Lemma 3) for controlling the reference settling error. Furthermore, the revised G2 and G3 introduce non-adaptiveness. only through their weights, allowing to apply
23

---

round-wise approximation methods [113] to bound them. For the revised G2, we approximate it with
N
Σ R=1
(1 (1,07.
feai aesosm in) (Vi++1
(.R.AA)) h+1
7m
where all elements adapt to the data generation process. The approximation error can be controlled via round-wise concentration inequalities (see Lemma F.5). The summation with regard to the revised G4 can be bounded through decomposition into four terms Ra, R3.2. R3.4 and R3.5 in Lemma I.3 following the same idea. For more technical details, we refer readers to Lemma I.2 for the analysis of the summation of G2 and to Lemma L.3 for the detailed treatment of the summation of G1-
Using the surrogate reference functions not only solves the challenge of simultaneous non- adaptiveness but also yields a log(SAT//p) improvement over the current ffut--of-thh-ar Q- SalyySettee-AAdvaaaaa [50] single-agent RL. by avoiding using the empirical process.
To our knowledge, this work represents the first successful integration of the surrogate reference functions and rose approximation handle both forms of non-adaptivvenss of the weights and the settled reference function. This methodological advancement significantly expands the analytical tools available for federated reinforcement learning and overcomes limitations present in previous approaches.
D Graphical Illustrations and Notation Tables
In this section, we provide graphical illustrations and notational reference tables to enhance compre- hension of our algorithms.
D.1 Graphical Illustrations
In this subsection, we present some graphical illustrations of our FRL framework and round- based design. Figure 5 presents the central server's initialization phase, where the central server broadcast key parameters to all agents at the start of each training round.
VLLk RRk
Agent 1
V. h
T NK
n .Nk Vk L,,k R,k h
Central Server
Agent 2
k N Vk LL,k V
:
R,
Agent M
Figure 5: Central server broadcast protocol. At the beginning of round k. for any state-ster step pair (s, h) E S x [H], the central server broadcasts the current policy n the total number of visits before round k N (s. (s)), the esstimmates V (s, T) (s)), the lower bound function v-l. (s, (s)) and the reference function V.R.k (s, (s)) to each agent.
The following Figure illustrates the agent-to-server data transmission phase. After exploration terminates in round (when condition (3) met), each agent transmits the rewards and some local summary statistics to the central server.
24

---

1,k and six local sums
Agent 1
Th n
2 Th n and six local sums
Central Server
Agent 2
Thu nh M,k and six local sums
Agent M
Figure 6: Agent-to-server data transmission. At the end of each round k. for any state-step pair hs S [H]. agent m sends the reward Fn (s, . (s)), the number of visits round m.kk
n (s, (s)) and six local sums in Equation (4) to the central server.
The following Figure 7 explains our round-based design for infrequent policy and value function estimate updates. Unlike conventional per-episode updates, our algorithms accumulate trajectory data across multiple episodes within each round, updating both the value function estimates and policy only at the end of each round.
Initialize n², T2.0 = V/ VRR.1
H. V.L.
Round 1
Update n2, 2h 1/2, VL2 vR
Round 2
Update T:3 1/3 VL v.
Update n oh V. y LK VRK R.
Round K
Update K+1 0 K+1 VV
LLK+ yRK+1
V/
Figure 7: Round-based design. At the beginning of the learning process, the central server initializes Q}. V/1 V-R.1 H and V/ 0 and chooses an arbitrary policy n1. At the end of round k. the central server updates the policy *++1 and (Q)+11 v4+1 pL.k+1 V yRR++I for any visited state-action-step triple (s, a. h) E S Ax [
25

---

D.2 Notation Tables
In this subsection, we provide two notation tables of Saddo-FartySSetled--.wwoo to enhance the readability of the paper. One of the table consists of global variables utilized for central server aggregation, while the other table presents local variables employed for agent local training.
Table 3: Global Variables
Variable
Definition
Qh
the estimated Q- value function of step h at the beginning round &
Q
the UCB-type Q estimates of step h at the beginning of round &
k
the I.CB-type estimates of step h at the beginning of round A:
the ifference-advantagee-e
Q estimatee of step the beginning of round
Vi
the estimated V-vulue function of step h at the beginning of round k
VL
the lower bound function of step h at the beginning of round & the reference function of step h the beginning of round l:
R
Vi
the advantage function V R of step h at the beginning of round k
B
the Hoeffding- type cumulative bonus in round
the reference-advantagee-.ee
cumulative bonus in round
[f, a)
the total number visits to (s, a, h) before round k the total number of visits (s, h) in round l
n (s,a) a)
Ph (s.a)
R.
the mean of the reference function at all next states of the visits to (8, a, h) before
round
R.k (s) (s,a)
the mean of the squared reference function at all next states of the visits to (s, a, h) before round
%h
Ph (s,aa
A.
the weighted sum of the advantage function at all next states of the visits to (s, a, h)
before round
of A (s,a)
the weighted sum of the squared advantage function at all next states of the visits (s, a, h) before round
(s,
the mean of V all next states of the visits (s, a, h) in round
U/ (s, a)
the mean of A at all next states of the visits to (s, h) in round &
Pb (s, a)
the mean of V- at all next states of the visits to (8, a, h) in round k:
0 N.N (s, a)
the mean of A (V2 all next states of the visits to (s, a, h) in round k
1 (s,a)
the mean of V/A.A at all next states of the visits to (s, 0, h) in round k
oh as)
the mean of (V/ (V,A,)22 at all next states of the visits to (s, a, h) round k
the indicator used to terminate the reference function update.
Table 4: Local Variables
Variable
Definition
7hp m.Kk
(s, a)
the total number visits to (s, a, h) of agent m in round k
Vh m.kk
(s,
0)
the mean of V all next states of the visits to (s, a, h) of agent in round k
Up a))a)
k.
the mean of Vil at all next states of the visits to (s, ft) of agent m in round k
Ph.r (8, a)
mi,k
the mean of vi at all next states of the visits to (8, a, h) of agent ra round
-ii (s,a) a)
the mean of (172 at all next states of the visits to (s, a, h) of agent in round &
Pb, (s,a) a)
mi
the mean of V,A. at all next states of the visits to (s, a, h) of agent m in round A
haa (8, .)
m,kk
the mean of (V7,, at all next states of the visits (s, a, h) of agent m in round i
26

---

E
General Theorems
Theorem E.1. Cb. Ak E 4,, almost surely. Then for any N E N and e >> 0, it holds that:
Inequality). Suppose ) is martingale and X Xk-1 S
e²
P (IXN Xol E) 2 exp
2 2
===1
Theorem E.2. (Freedman's 's inequality, [49, Theorem EC.I]). Consider a filtration Fo C
and let Eg stand for the expectation conditioned Fu. Suppose that Y,, Lk=1 Xx E R. where {Ka} is a real-valued scalar sequence obeying
Xx S R and Bk-1[Xa] =0 for all k 2
for some quantity
DC. We also define W,, Σi=1 Wn o² holds deterministically for some given quantity o² co. Then for any positive integer
In addition, suppose that
m 2 1, with probability at least 1 - 6, one has
0² 2m
2m
2m R log
Y 1
8 8max
W
log
8
Theorem E.3, ([109, Lemma 10D). Let X1, X2.... be a sequence of random variables taking value in [0,0] Jj. Define Fs = (X1, X2,..., Xx) and Yv E[Xx| 1) k 2 1. For any 8 we have that
PP
72
X 3
Yk + (log(1/0)
5
k=1
k=1
and
3n
Yu 2 3
Xx + + 10g((1/))))))
86.
F Key Lemmas
In this section, we introduce some useful lemmas. Before starting, we rank the visits to any given triple (s, a, h)) based the "round first, episode second, step third, agent fourth" rule (time order) and use ks(s, a, h), j'(s, a, h), m' (s, a, h) to denote the the round, episode and agent index for the i-th visit, respectively. When there is no ambiguity,
use kt, m', and j for short.
Let X = (S, A, H,t,) The notation f(X) S g(X) means that there exists a universal constant C 0 such that f(X) < Ci)(X). In the following sections, we assume that 0/0 0. For any CE N+, we use [C] to denote the set {1, ..., C}. We also use I[z] to denote the indicator function, which equals 1 when the event is true and 0 otherwise.
We now begin introduce lemmas. Lemma F.1 establishes key relationships between certain quantities used in Algorithm 1 and Algorithm 2.
Lemma F.1. The following relationships hold for Algorithm I and Algorithm 2.
(a) For any (8, k, k) E S Ax [
[K], we have
(s, a) < max {1
( a)
m.k Th
Vm E [M].
MH(H +1)
and
(s, max {M. M.
(s,
+1
If (N) 200
(x) < (s,a))
H(H +1)
(b) Let Ti (+m(FT)) To + MSAH, then î < T, S 2 + MSAH.
27

---

2; H (c) K -
(d) For any (8,a, E Ax [H], NK+1 (8, s
Proof. (a) is obvious given Equation (3).
(b) According (a) and the definition of To in Algorithm 2, we have:
f Σ NK+1
(s,a) - Σ
No (s)
+
Σ
nh (s,
8,0,
s.a.h
8.0,
To
H(H No (s. + M Tí.
s,a,h
The right side is obvious by noting that To < given the Algorithm
(c) It is proved by K < - म S
Ti H.
(d) It is because N₂ (s,a) Eea N 1 (8,
= 4
In the following Lemma F.2, we will present some properties of the weight r//.
Lemma F22. The following properties hold for all E N+:
(a) For 1 & a & 1, 1/1a S Ei=rt// $ 2/ta.
2
(b) max v $ 2H/1.
(c) Ee n/j = 1 1/H.
(d) For any t E N_ and i E [t - 11, 1/+1/ = 1+ H/1 1.
=
(e) For any E N4 and any (s, a, h) E x Ax [H], ift < as, = and ( a) 2 in.
No. /vf S exp(1/H)
we have that 1/1"
Proof. Here (a) is proved in [50, Lemma 1]. (b), (c) and (d) are directly from [113, Lemma B.2], so here we need to prove property (c). Note that
N M
(1) I nN
((--N)) (II)
N WO
II
(1 (1-m))-
(1 -
S exp((1/H).
TI
Here (T) is because 74 is monotonically decreasing. (II) is because i (s, S (+ S
(s.0) for (s, a) 2 in by (a) of Lemma F.1. The last inequality uses the definition of 7 L
H(H+1)
Next, we define the new weights (s, a, ht) for any n1 <i ne s t N4 and any (s, a)
e
S x A [H]. where n NE (s, and n2 No +1 +1ss, a):
(s, a, h) = I// < <b) + 1- (n1 1, n2)
17 ( + 1,t)[[m 2 in).
(19)
n2
m2
We will use the simplified notation iff when there is no ambiguity. In Lemma F.3, we present some key properties of the new weights 7ं and their relationship with the original weights o/f
Lemma F.3. The following relationships hold for any hs,,hhkk S t= (s.
A H
[K] with
(a) For any i [t), if as) (s a, h) and N (s..h)))))) (s, 2 in have that jf (s, a, h)) Th as)
28

---

(b) For any k' < k and k' E [k], we have that
N
N
a) =
Σ
n
P=NT
N=
+1
which indicates that Ei=1 !i = 1 0].
(c) For any i E [t], we have that
h//l S exp(1/H).
(d) For 1 = Nh (s,
4 Σ 1=t+1
G )2
th /Vii
1=
Proof. Here, (a) and (b) are directly from [113, Lemma B.3] and (d) is from [113, Equation
(19)), we only prove (c) here. (d) of [113, Lemma B.3] proves that of S exp(1/H)mf when No (s, a) 2 ig. Additionally, by the definition of rî (see Equation (19)), we have i nj
when 2a (s,a.) (s, a) iv. Combining both cases, the proof is complete.
Next, we develop an immediate corollary of Freedman's 's inequality.
Lemma F.4. Let log( 2S.AT.) for any (0, 1). For any (s,a,h,k) E S Ax [H] [K], let (Wht h+1 E RS 1 < < (s, and [ut (s, a. (s, E E iisis (s) be collections of vectors and scalars, which obey the following properties:
Wh+ is fully determined by the samples collected up to h-th step of -th episode of agent m' in round ks, where the samples is ordered based on the "round first, episode second, step third, agent fourth" rule (time order).
/Witills I Cww
a, as, NW) is fully determined by the episodes collected up the h-th th step of j -i episode agent m² in round k2, and positive integer NŁ E [Tr/ H). The samples is ordered based on the "round first, episode second, step third, agent fourth" rule.
S as, NR) S CN(N)).
. 0 -S (F( (8, a, No) 2
With probability at least 1 - 5, the following inequality hold simultaneously for all (s, h, k) x Ax x [H] x [K].
N
u (s, N/) (1 (Leegtime Parac
Σ
Wokt 1++1
No
(Vouaat) ( No + (,
5 Cu(N Σ (s, V.V. & b41) +8
Proof. For any N₁- = N = [2/H), it holds that
Σ (s, a, N2) (1 (1 -Paan Whi Σ u (s, (1 (1
-aaan Whi
X/ I'm
(de 5' ((k N JN J.mNN
29

---

where
xx m'm jedi
un (8,0NN) N) (1 Lerggim
Pxaa,)) im W Wh a)ll (sh 5'm an K. (s, a)
h11
Here, (W, h, m') I (N- jr h. m means the sample at (k', J h, m²) is collected before the sample collected (k- . h, with the order "round first, episode second, step third, agent fourth". jk I' mm is the number of visits (s,a) at step before the sample (k', J h, m'). We order h. 18,,,h,k, N) EEEEAAX [H] [T/HH] (T/HH, we
x x-''"" ''mm' to be (Y1, y,.... Y.). Then given (8,0,
have 1 It also holds that:
[X] S | 2 S C,(),,
and
Σ E, Y2? [
$ $2C,(N))
Using Theorem E.2, with R (N)( m log2(N), 0² (N)C have, with probability at least 1 8/SAT?
2 as, (1 (Iglghime Paiai) W
24 max [u)((s.a,))VVsaa (C,(N)
+ (C,(
N
5 Ca(N)4 Σ N..ss.aNNV +8
Cu(NNC
N + Ca(N)C
1=1
Consider all combinations of (s, E Xx | D
11,, finish the proof.
Using Lemma F.4, we derive an upper bound for the summation of non-mon non-martingale differences weighted by v The results are presented in the following Lemma F.5.
Lemma F.5. For any (s, a, k) S A x [H] [K], let (W h41 S iisis (s, a)} be collections of vectors, which obey the following properties:
Wh k+1 is fully determined by the samples collected up to h-th step of j episode agent m² in round k3, where the samples is ordered based on the "round first, episode second, step third, agent fourth" rule.
W I Cw-
Then with probability at least 1 the following inequality holds:
N
N
_N 11
Leggtme - IPs,aal PPs.aa)) W 9441
S
Hi
7
Nk Nhw.
Ve (W.ttt +
HC No.
1=1
W
1=1
H
Not V
HCw No.
1
s. s. (Wi+1)+ +
N
Proof.
N
No [ Le - Paaan
Whin
Σ
N/
N
No
}
(1 - Parann whi
11:
11:
1):
1/
s
30

---

We know E 7ii No 2HH/N and Σ with (N()) = 2H /N, with probability at least 1 8/2. it holds that:
Ny No _ 1 from (b) in Lemma F.2. Using Lemma F.4
N M
N Hi
I.s, Pssaan Wh++ E
1/s
N
HCCl s.o.A ht +
(20)
No.
h
For the second term, let {ki < h < <.. &i
< hit v
K}
be the collection of round indices that
h (s, a) > 0 for any E (t). Then we have:
No 4
11:
Nh)
(1 (1 -Pa, Paaa.
Whit
n (N
kn+ + 11,
Σ N
N
(
[ hht
Whit (21)
7i
77
n=1
For Nk.+1 < iu, since f
No
Noati
N N
No Nhatt
11
12
Amngptms - Pe Peaii)
W O.
17
N= N
For Noaat +1 know
2 and i [N + 1 by (d) of Lemma F.2 and (a) and (b) in Lemma E33,
Noh N
Nhu+t N 11 N
+
N
No+ UNt
Noat1 I1 NN
1/4
11
11 N and thus 1/
1/8
Then for given Nh,t1 N2 [o,Ti/H), N Ni E [0, N2). and (s, a, h, kn. n) E S Ax [H]
[T/H H
No [THH], using Theorem E.2 with R 2C (1) (N m [log2(N2)]
No
0² = (N
No
) with probability at least 1 - 5/28 ATT, it holds that:
No
N
No
P Ps.a. Why
173
Am Nff
NNa - n/
V aa (W heile (1/52 -7N Cwv
No
1/e
i=
Consider all the possible combinations of N = N₁ E [Ti/H], N = N₂ E [Ti/H] H and
(s, a, h kin) E A x [H] T HH, with probability least 1 - 5/2, it simultaneously hold for all (8, a, h kn, n) E S x x H x [T/H) x [Ti/ H] that
N
1h
T
Anit'.m P. Fe,a,n) Ahol
hhe h+1
i= Vin
Nhat1
Nda
2
Nbatt NNott
Nhat1
7
n1;
V (W
n
"I
Owe
i= +1
V..a (W
(n
Adott A (N
Ndett MN +1) Cul.
N
31

---

Here, the last inequality is by (d) of Lemma F.3. Applying this inequality to Equation (21), then
7
N
11: wx
Pa Peaai
Wh+t
Nauti
1= 7' (N + 1,)
V Va (W +
N
UN. +1
Noa+!
Cart
Vi
N
Mi N
Va
1 N
No.
) Cral
Vi
Nn
- - NN
Noh +1
n=
No
No No
Cwv
N
N
N
1
Σ
T
No
Va,an (Whht2))))))
++
No Cwu
No V a, (.
HCwb N
N
7
+
(22)
In the second last inequality, we use the Cauchy-Schwarz inequality and the monotonicity of 1/2 N We also use N No because there is visit to (s, h) from round k + 1 round k - 1. The last inequality is by (a) and (b) in Lemma F.2. Combining Equation (20) and Equation (22), we prove the first conclusion. Moreover, note that:
N aa (Waet
(+tt) = Σ
V Va h+11
n=1
M
V V.
h+1
th
V V.,, (
==1
N
The second equality is because (b) in Lemma F.3. Then we finish the proof.
Lemma F.6. For any non-negative weight sequence (w a [0, it holds for any h E [H]
k.j. [I E [K], m E [M], [nmm. and
that:
k.j.m wh
N
N
(s
an
[0 < N/
(s
k.m. k.m. < M)
2"
k.j.
(SAl[W]]>o,)) ||ll
Wh
( ,0 mga
--a a
k.j.m.NN
2a
< 22MSAlllloo,,
1-a
Here, || = max (oaxx J. and ||o||| 1. = En.go
wh k.j.
k.j.m
For for any h E [H], we have the following conclusion:
Σ kal.m J.J.
S 2MSA + 2S..
(s
.a
N
32

---

Proof.
k...m
p.j. wh
Σ
Σ
Tistiimm :a .a.dim) (s,
(5
(x)
k.j.m,N
8.0 k...m.
We decompose the summation into two terms
E
Wp
11(s% dh k.J.m) = (I N < <M] + 2 M))
k.
(N) a))
8,0 R.j.m
Let (o(s, a) max(k 1 isksk K, No (s, < M}. Then for the first term, it holds that
k.di wh
t... an -.imm (s, a) < (s. M]
(s a))
Rj.m
$ |
Σ (((s
kimm a b.3m)) = (s, a) 0 < (s, < M
kigum
No =|Wlloo,h Hidmm a.a. my = (s,
1= J.m
=Iwolbo,, Noo a) S 2M 1woloooo
(23)
and thus
ΣΣ k.j.m
Wh 1(0 f.mm ah Addm) (s) NĀ < M] < 22MSA//ullo,, (24)
(s)
R.j.m
For the second term, let
c)(s,a)= = Σ wh
kidim
(s, a)] (s, 2 M|
k.j.
Σ w (
k.j. oh k.j. = a)]
Am + J.m
Then we have E., (s S Ekj.m
k.j. 11 Given the term
k.j.
Σ k.j.m
Wh hi
an -. (s,
(s)
k.j.m concentrates smallest round indices with largest values of (x.)) we when the weights w, can obtain the largest value. Let ko a) < ki < k2 <.. < ke S K be all round indices that satisfy Ri (s, a) > O. Then we have:
n,
(s, S Wolkh
Σ
krim .hh
k.d.ma = (s) = |
ki n (s,a).
Rim 1o+t1 j.m
1=1
Let
n (s, ( (c
q max a 0 110599511 |||loo,
and
d = en (8, a) |W]|ooo
n (s.a).
33

---

Then for < t, we have the following inequality:
T((5 tm aa (....m) = (8, () [N 2 M]
(N (s, a))a
R.d.m
ki ())
d
W (N as,
(25)
Note that for any 0 < y < x and a E [0, 1). have:
1 (xt-a -yt-a).
(26)
xa
Then, for any i e [t] let N (s, a) and y = N (s, a), it holds that:
n Ns (s,a) (N a))a
22a n (s, 22 (s, (8, (N (s)
(N (s, ( ())
(27)
1-a
Here the first inequality is because No. (s.a) (s, + n (s,a) S 2N (s by (a) of Lemma F.1. Summing up Equation (27) from to g, we know
8
ki (s.a)
(N h
(s) -a (aa)))-aaa
(N (s, a))
I 2a
(s.a))
1
i=1
(N (s, (),
(N (s, a))
S 2
1- a
i=1
(Nohot) (s, (s,a))
(N (s. a))
2"
1
1-a
1-a
Li=1 n ki (8,
2
(28)
1 1-a a
The second inequality is because k; + 1 < k441 and thus N < N (s,a),
a). The last inequality is because for any x > 1 and 0 S a < 1, we have the following inequality
(s.
x S (a 1) +1,
and we can let N (s, (s, a). Applying Equation (28) to Equation (25), for q < t, we have
k.J.
Σ k.j.
R.d.m = (8, (s, ( 2 M]
(s, a))a
1-a
Ei n (8,
d
< $20 | ||ll oc.1
1 1
(N
(Iwllooh Eim nip
Rs (s,
I-a
d
< (2)
1-
(N ku +1
(s, wwllo,))))
1-a
(IWlloo,h E1 n
fi (s,
d
< (20
1 Ck
(ca(s, aa)
< (2]lw]loo, (
(29)
a
34

---

Here the second inequality is because / (8,a) S (s,a) for q < and N (s.a) >
M. the second last inequality is because on (s,a)) a) I Nt Nffitttt (s, [)llwl by the definition of q. The last inequality is by Equation (26) with r = ca (s, and | Ei= " (s.
We also prove the Equation (29) directly by Equation (28) for q with d = 0. Therefore, with Equation (29), we can conclude that
k.j.m wh
ΣΣ (Ni a))
k.j.m
d. (s.a)]I (s, M)
s,a k.jm
2d 11
so.
2
(c)(s 1a - 1-a
(SA)
W ||
(30)
6,0
The last inequality is by Hölder's inequality, as Es,a (s a) S || Combining the results of Equation (23) and Equation (30), prove the following conclusion:
J.
2a
Σ
S 22MS +
1 (SA)
NE (5
R.J.m, 20
For = 1, it holds that:
Σ kijon k...m)) k.j.m
K
n (s, a) (8,
Ko
n
(s, a)
Σ
Σ
K
( a)
(s a
(8,
8.0 A=1
8.8 k=1
8.0
k=
Let w/ k.mm
= By Equation (23), we know
ho
n (s.
kp n (s,
2M,
- 2MSA
(31)
(s,
(s)
5,a
We also have
n (8)
K
n (s)
22
Σ
(s)
1 (s,a)
k=
h=
2
Mog((N>-'sss (og
log(N)(s
k=ko+1
< 2loggTT)
(32)
Here the first inequality is because for k > ko(s, a), (*( a) 2 M, we have 1 a) 2. a). The second inequality is because for 0 < < x,
s
< log(r) log(t).
The last inequality is because N (8 < Ti To summarize, combining the results of Equa- tion (31) and Equation (32), we then prove that
Σ kid.
S MSA + 25A log(T) < MSA + 25A.
(s a k.j.m
k.jm
G Probability Events
In this section, we provide some probability events for Fedd@-EarySSetee--LooCCttt
Lemma G.1. Define (y (s) := max (V) (in + 8, v/t. (s)}} for any (s, h k) e Sx (H] x [K]. Using V(s a, h, k) as the simplified notation for V(s, h, k) S A x [H] [K].
Then we have the following conclusions.
35

---

(a) ([113, Lemma C.I)) With probability at least - 6, the following event holds:
E1 = f (s, (s, 2
(b) With probability at least
6, the the following event holds:
N 7/
8
.N
(m - Pe.ee))) ( (Vits - V
R,,e"
h+1
n=1
S
No
Hi
Oh
A.k
(u )
+
H2
No
V(s, a,,,,,
(c) With probability least
8. the following event holds:
N
NAP+1
(1 (agigtim - Perun)
VRai Vnti
2 (uRAA))
H + NE
R.
On
N
(d) ([113, Lemma C.3]) With probability at least
6, the following event holds:
(14m) - Poojatt Vhtt S
H
E4
v(s, a, h,
N
With probability least - 8, the following event holds:
H
Es
Σ
(e
(et)
P P.p.a.m ,0 k.J.m
k.a.
(Vh+1
Vith $ 27 2HTT
Rigio
(f) With probability at least 5, the following event holds:
(1,9 ....a))))
Vi+1
2r
E6-
H "V N)(s,
())
(g) With probability at least 1 - 8, the following event holds:
Σ (1 (14mgmmm mm Po.e.t) (Vit1)²
2 () (s,
E, =
S H2
(s.
(h) ([113, Lemma E.6]) probability least
6, the following event holds:
Es
k.sm kmmo (V S HT, H
k.j.m
ii) With probability at least - 8, the following event holds:
Eg =
P
P.tsi Patsmmmttssmmm
(Viini Viti) S V2H2TT4
2x11
1=1 Aug.m
36

---

ii) With probability at least - 8. the following event holds:
E10-
V
(s & /SATIT AITL++MHSSAV MHiSAVi
A=1 Ridim
(k) With probability least
8, the following event holds:
E1 =
Σ
sism
A {(Vi+= -Vh+-i++---- ( - - (5++1 (.mm)))
88]
h.k.f.m
(Vh+1
( (++11 t
[
k.im vilhht ($
3 Hi
k.j.m
(I) With probability at least
8, the following event holds:
(PRtn Viita)
E1
Light Paran))
N
N
2
B
(s,a,,
No
4T
(m) With probability at least
- 8, the following event holds:
Ny 11
E13
1
Σ
1 Leighmm Ps.a.) Viti
N
2=1
THe V V.san (Vitz))
4
41 ((s,a,h,kk,)
Noh
(n) With probability at least
8. the following event holds:
E14 =
. (1 Mm
IP k.j. aatiimm
(. an) (Viti -
PR.
A+1
Hi
BHe NE
S
B
v(s,a,1,k)
NE
Proof. (b) Using the Lemma F.5, with probability least 1 5/2, we know that for V(8, a, h, k):
N
1 1. P Po.a.h)
(v++1
V,R.AT)
N H
No s.ah
H2,
N n=1
(v/t1 - Vh+1
+
N
(33)
Next will bound the difference
No
h
mm
V.
s.a (VhtI
V-R.A"))
(oA. A. (1 2 NA (oA (2..
where
N
XA
Σ
Th
Nok
Vsan
(Vitfz
V.R.A
h+1
n=1
37

---

Based on the update rule of Equation (8) and Equation (12), by recursion, we have:
N
N
No
.m))
A,k
(vit)
verl 3
4rt m²))
The
h+1
h+1
h
The
n=
(34)
According to the definition of Vs,a,hs we also have
Vsaah (VATL.
V.R.k 1++1
Ps..h (Vitii
V-R.A")
(P (Vi"),
V.R-A ))
(35)
A+1
h+1
Combining the results of Equation (34) and Equation (35), can decompose the difference 41:
N No
1
(Ps.aah - 1n gmmn.gm.mn
)
(va")
V.R.A")
sh12
h+1
N
No
+
(V
h+1
6"t 5" h+1
m)))))
(Pean(Vif)
h+1
)²²
(36)
For the first term of Equation (36), with Lemma E5,, with probability at least 1 8/4, it holds for V(s h, k) that:
N
7n
No
IP s,
1 1m )m S/44
(v
VRA
N
NA Ve (vem - V.R,en)
H&L
N
h+1
+
N
==1
N
H
Ni V.V..a
(Ver V/8-11))
H3,
N
Mm
+
No
n=1
H3,
H
X
(37)
No
N
The last inequality is by V (x,x,(( < 40 4 for |X| C.
For the second term of Equation (36), since V S Vi-i by Cauchy- Schwarz inequality, we reach
R,K"
No
2
No
Σ
(V
- VRAA") ( (oh*t (m"
Σ
N 1/m
(Feaa.
- V-RAA")
Tn
n=1
n=1
Nx
N Σ
Σ
7/1
Nok
(Vati
Vi-it (sht1 (1 mi))
in
No
IP
s,aan (Vitt
V.R.A.)) )
< 2H
Σ
N/ 2
Nok
(1 Polai)
(Vati
v.R
h+1
H XA
3
+
(38)
N
N..
The last inequality holds for V(s a, h, k) with probability at least 1 5/4 by Lemma F.5. Combining Equation (37) and Equation (38), back to Equation (36), with probability at least - 5/2, we know
I = XA - (AA. (1 (1
-(aA
H3t
1
S
X
NE
NF
38

---

Solving the inequality, with probability at least - 8,/2, we have
H
XA
%
(1
N%
Applying this inequality to Equation (33), with probability at least - ō. the following relationship holds for V(s, a, h,, k)):
N
Σ 1=1
No 7m
(1
(1gggrmm Ps,an)) )
(Viti V.R.A"
S
No
Hi
On
A.k
- (m)
+
H2
N
(c) To begin, note that
N
No
Mn
Σ
Vh+1
N
NM
Σ
fh
N
N
NW-1
1
Σ
*1.1
Pp aean
VR
N= +1
N
NW
1 Lisgi *h41
IP Ps.a.
N
NE-I
N= +1
eegiim - -aaa. h+41
VR.d"
(39)
For any given (s, and N N E H], using Lemma F.4 with Cu and C 2H, with probability at least 1 8/25ATi. it holds that:
1/N
N N
p Σ
Va,, R. h+1
Nr*+11 +1
Σ
(Leighime #++
1
h+l
+1
No
N h
H.
(40)
Consider all the possible combinations (s, as,a,h,N) E SxxX [ x [7 we know with probability at
least 1 8/2, Equation (40) holds simultaneously for any (n, 9, a, h k") and N N [H] Therefore, applying this inequality to Equation (39), with probability at least 1 8/2, we then have:
N
Tn
Σ t=1
11gggtm - P. Ps,a,
1
VRR
N
R=1
N
Vea (sa.n(VRe (RR
H N
Mh
N +1
(41)
For the first term of Equation (41), by
inequality, it holds that:
N
k. R.
N
No
N
V.
(VR.A R
Nk
Σ
Ma
Σ
N
h+1
nn
+T
N
T
n=1
n=
(42)
By the definition of kt, we know Nok +1 2 and then by (a) of Lemma E22 with = 1, we have
N
N
Th
(43)
N P
n
==
39

---

and
Ni.
No
v. (V h+1 No. +1
Nº
Ni. Un
Th
N
N
V
(
s.a.
(VR A+1
1
s.a.h (VRL))
(44)
h
Here, C, {n: NA
2 i S )- Applying Equation (43) and Equation (44) Equation (42), then we can bound the first term of Equation (41):
N
Va h+1l Nh*+
N
N
s,a, (V
7/n
N
N
For the second term of Equation (41), same to Equation (43), we have:
No
He
He
N
h
Applying these two upper bounds to Equation (41), with probability at least -6/2, know that
N
N
N
Σ
(Aaigh.m - -PP.a Feah
R,K h+1
S
N
N
Va
V
h+1
+
N
Hr.
(45)
==1
m=1
Next will bound the difference
1=
Σ
1
V
s.a.h (VR..")
(RR (H)
A XR
(0 (2)))12)
h
where
N a
XR Σ
V
(V
h+1
N
==1
Based on the update rule of Equation (6), by recursion, we have:
N
Nok
RR h+l
(s4+1
(" m 3
R.K
(vRRA))
( ( mm")
(46)
N
No
n=1
According to the definition of V s,a, we also have
Vanah (VRA4)) Ps.a.
(IP
1R,b* h+1
(47)
Combining the results of Equation (46) and Equation (47), we can decompose the difference Tz:
Nt
1
R, 2
(Paian
1 pmmmpmm
N
No
N²
Σ
RR
( mmammm))
Σ
1
(P..a
(48)
NE
NE
h+1
For the first term of Equation (48), with Lemma F.4, with probability at least 1 6/4, it holds for v(s, a, h, k)) that:
N
N
(Pa,a,h 1 (mnngnmmm))
Vannh
(p.RAn h+1
+
2
N.
N
N
12
H2t
1
(VR,EN
H2
N
N
Vea.h
h+1
+
N
==1
H
H²
XR
(49)
No.
N
40

---

The last inequality is by V (X22 I 40 s,, for |X| I C.
For the second term of
Equation (48), by Cauchy-Schwarz Schwarz inequality, we reach
Σ
RR
A" (mmmm)
And"mm"))
(Pr
N
h+1
$141
No
h+1
n=1
2
Σ
VR, R,
a,a.h V.Rk h+1
Nà
h+1
No
==1
S 2H
Σ
sm Ps.a.)) h41
V/411
N
n=1
H
H
XR
+
(50)
No The last inequality holds for (s, a, h, k) with probability at least 5/4 by Lemma F.4. Combining
No
Equation (49) and Equation (50), back to Equation (48), with probability at least 1 - 6/2, we know
1 = XR - (o
R.K. - (1h (2
2
H
XA
2
N
N
Solving the inequality, with probability at least - 8/2, we have
XR S (hh
R.K
(1h ()))))))))
H²t
N
Applying this inequality Equation (45), with probability at least 8, the following relationship holds for V(s, a, h, k):
N
N
Σ
1
Ml - -Pasn Pannh *h+l
Vh+1
H
R.K
(1
R.A
+
H
NE
N
(e) For E,, the sequence
{ (P..... (......m. kn
k.p.p
h+1
Vitti R.j.A.m
can be reordered martingale sequence based on the "round first, episode second, step third, agent fourth" rule. The absolute values of the sequence are bounded by 2. After appending multiple Os the summation such that there are terms, the sequence is still martingale. According to Azuma- Hoeff-dng inequality, for any 8 E (0, 1), with probability at least 1 - 5, it holds that:
H
i hh-1
Σ A.jm
(P pamm oa
(Pat
k.s.m nn 1..m
(Vitt Vxt1) s 27 222T1.
(f)
Ps.aah
Vi+
nEN+
is martingale sequence bounded by H. Then according Azuma- Hoeffding inequality, for any E (0,1), 1), with probability at least 1 8/SATi, it holds for a given N a) = E N4 that:
N
2
Σ
1
en p" - (Ps..h)) A11
Vitt1
S H
N
For any l: E [K]. we have N/ a) E [. Considering all the possible combinations (s, (s,a,)) h, N) E
A
H
x
411. with probability least 6. it holds simultaneously for all k)
x A
x
X that:
N
2
mm -Posaih Vřrn
<
N
hhil
N (s.
41

---

(g) The proof is similar to (f) with
gm -P Praa) (V (V nEN-
being a martingale sequence bounded by H!2
(i): The proof is similar to (e).
(): The proof is provided in section C.3 of [113] when bounding the term Σ 84.
(k) It follows by Theorem E.3 with H.
(I)
Aist P. s, *h+1
Viit1)
mEN+
is martingale sequence bounded by 3 Then according to Azuma-Hoefinn
inequality, for any
5 E (0, 1), with probability at least 1 -5/SATT, it holds for given No +1 (s, a) = N E N4 that:
M P. Fsaah)
Vie..) S BVV
2
For any kn [K], have No + a) [#). Considering all the possible combinations
(s, a, h, N) E ESX A x И x
with probability at least 1 8, it holds simultancously for all H that:
(8, (s, h km)
ESX Ax
Prain) ) (ranh - Vhit1)
2
S SBV N
N
(m)
{ (1eggtm Psaah "141
Vh+
nEN+
a martingale sequence bounded by 2H. Then according to Freedman's inequality Theorem E.2, for any d (0, with probability at least - 8/SATi holds for a given N *y*++(ss,) = N N, that:
Vaa 1e
7He
P. Po,aah
Vitt1
S <AV
N
N
Here set WN NV a. 1itt), R= H, m (Ti) and 0² H.
N a) E [ Considering all the possible combinations (s, h, N) E S x A x H x [ with probability at least 1 - 8, it holds simultancously for all
For any An E [K]. we have Nk" (s,
(s, (s, k) E S A [ K] x [Ti] that:
+1
W Va Vittie
7H
V
Vitti
S 1
(n) By Lemma F.5, since 0 < P.R."" h+1 (s) - Vi++(() < 3, then with probability at least 8/SATi. it holds for a given (/, a) = N [Ti/H] that
Σ
pm Po.a.) (Viiti
ARRAA A+1
S
H
m N.aaa, - pR. +
3Hc (1)
<
3
H
BHc N
N
N
N
Here, (i) is because V k.m. f.m. (Vit1 h+1
< 3 and Σm
7n No.
< 1. Considering all the
possible combinations (s, N) E S A
H x Th we finish the proof.
42

---

H Key Properties of estimated Q f-uuction and V ffnnctions
We first prove the optimism property of the estimated Q-function (s,a).
Lemma H.1. Under the event Ni & in Lemma G.I, it holds that for any (s, 0, ( k) ExxAx
[M] x [K]:
( a) (7, o) and (s) 2 (s).
Proof. We use mathematical induction & to prove (s. a) () and (s) (s) for any (8, a, h, k) E S x A x [H] x [K].
For h = 1, (s. a) H 2 Q% a) and (s) = H 2 V (8) for any (s, E x A x [M].
For à > 2, assume we already have 0% (s, a) 2 (5, for any (s, (s,a,h,k) E EXXAx [ [K -1.
then we will prove for any (s, a, h) E x A x [H]. (s. a) 2 (8)
It is sufficient to show that
min { U. a). oh " (s.a)} 2 (s,sa).
The event & in Lemma G.1 shows that 0% U.k (s,a) 2 (s) Then it is sufficient to prove that
(s, 2 (s)
(51)
To begin with, according to the update rule Equation (11) and Equation (15), we obtain
Q (s, a)
No
No
(ra(8,a) (Vit1 - VR...")
R. +1. + B3Rk+1
Noo
Mn
hh4l
+ Pb
n=1
N
N
n=1
Since En 7a
= 1 by (b) of Lemma F.3, it leads to
No
2 R.K (s, a) ()(saa) = (H-QQ(3,a)) + Σ
Nk
bR.
ma
n=1
N
+
Tn
(8) + (ver - k+1
(hh-1
*"
+ M4
RI
-2
(52)
To continue, invoking the Bellman optimality equation (1),
(7,s a) = rn a) + Ps.,h Vhtt
and using the update rule of Ph R in Equation (6), we reach
an( + h// V.R.A")
k" """""mn" mm"
+
1h
RA
(s)
EM
N
VRRk'
h+1
-VVh
V.RAA"
Ps.a, Vini
+1
(V.R,**
RR
= P
Viut - Vitt
+
h+11
+ +
N
where we have introduced the following quantity
$ c (1:1 -Paan) (V V.R.A")
+
1
Leigitm - .Paaa.
V
9h41
43

---

Since kn < k - know h--1 +11+1 2 0. We also have V.R
2 for k k
h+1
because the reference function yRR.// (s) is monotonically non-increasing in view of the monotonicity of V (s). Back to Equation (52), we know that
N
2 (s, a) a) S
R h.n'
Sh
Therefore, we only need to prove that
N
Nk R Th h,n
Sh
n=1
Let {k1, ko,,.., ..., ke} be the collection of round indices that ni, (s, a) > 0 for any i E [t] and h k2 < ... < ke k. Let kn and k4+1 k, then for any i [t + 1], we have 3h. (s. oh
gR.hi-it1( (s, a) (ki- 0) and N (),a) = N N a) with ko since there is no visit to (s, a, h) from round ki-1 + to round k; 1. Then it holds that (Here, nf + 1,n) = for any n E N-):
No
No
hm
Uh
hm
(=1
n= n=N
N+++! -1 Σ
No
Uxatt
No
gR.n.
N "
gR
No.
R.2 N
Th
2
7h
11 NN
h
UNZ
11
N= wh
+1
==
R.2 No 17n
22L
(NV
+ +1,
(1V + +1,N
R=1
N
R.2 N
H2L
(M
+ 1,
N1))
R + (7V + 1,, 3R
+
1/n
==
No. 2
1126
R
h
c
(53)
n1
N
==1
The last incquality is because of the property (a) of Lemma F.2 with a 1. Under the event n Nime E
3
N
Σ
Mm
H N
o
(1A.))
N h
o
R.k
(1
R,K
)
2
H
N
h
Then for some sufficiently large constant
ch cn
O, by Equation (53):
R.2 H2,
N
3 R.k h
+
na
Uh.
N
R=1
n=1
Now we finish the proof of Equation (51) and thus Q a) 2 (8 Then we can conclude that
Vi = max (Q% a)} 2 max (Q) (s, (s) (*).
We have thus concluded the proof of Lemma H.I.
Next, we will present the pessimism property of the Q Q-estimates Q (s, a).
Lemma H.2. Under the event &, in Lemma G.I, it holds that for any (s, a, h k) E A [K]:
Q1 (s, a) S ()) and (s) S (s)...
44

---

Proof. We use mathematical induction on l to prove (s, - Q% a) and (s) - (s)
for any (s, a. h k) E S x A [H] [K]. (s, a) (s, - (h, a) and vil (s) 02 (s) for any (s, ES* A x [m]
For - 1,
For k 2 2, assume we already have Q (s,a) < (7,ss a) and wLk (s) I Vg) for any k,a,,,kk S x A [M] x [K 1l, then we will prove for any (s, (s,a,h) h) 8 x A x [M].
(3,a) & (5, and Vn vi (s) - (s)... Based on the updating rules Equation (10) and Equation (14), by recursion, since 2 (s.a) O, we have:
N
Q) = Σ N ==1
Th
(TA(s,a) + VLAA")
nn
ba-
To continue, by invoking the Bellman optimality equation Equation (1),
(5,a) a) + P. a Vi+1i
we have
Quaak (s. a) (5, a)
No
N
No
( (6h+1 mm"" - P Paan Vitt)
No. br
7m
Th
n=1
n=1
N
No
NY Σ n=1
Σ
No
("t"""mm" h+1 - -Vitt) (8/+2
+
7m
N
(11
.Psaa)) Vh+t
Mm
h by
h-1
n=1
N
No.
Σ
Na mm
(1grymm
- P Pa.a)))
Vitta
No 1/m
bn S O.
n=1
n=1
The last inequality is by event &g and
N bn = co V H3
N
7n
N
H
Th
2 cb
N
by (a) of Lemma F22 with by definition Equation (17) of (s). we know
1. Now we have proved that Qhit(s, (s, S (7(s,)) S (s). Then
Qhaa (s,a'), Va Vo."), (s) } S (V) a'EA
vr (s) = max
max
In the following lemma, we will bound the error between two Q estimattes Q a) and Q (s,
Lemma H.3. Under the event ni= Ei in Lemma G. for FedQ- MarlySSttle-LLowC.. algorithm and any non negatiee weight sequence (utt.. " In. it holds for any [H] that:
Σ k.j.
wh J..i
Rimm (0h 2%aa) (gh , ah k.s.m
H
S v HSSA||wol 1kllla +
J.im (h) (k)) Wh
k Kmch k.j.m
where for any h < 11 S H -1
w. (h) = w. k.j.m
J.j.m (h)
Σ
H I' ml (h)I
Ny
W I ((.". (k.
wh41
ot am
45

---

and
Vkjjm b
NW. H + HTTO "10
(*
< in] +
H N
T[o
< N
M).
V
Proof. To begin with, according to the update rule Equation (9) and Equation (13),
obtain
NR
N
(s, = 110
No
No (ru(s,a) + V (5 of f
bi.
h+1
==1
Similarly, according the update rule Equation (10) and Equation (14), we obtain
No
N2
2 2te (s, = >n
th
N
(T)(s,a) + h+1 (9/1
Σ
n
b
1=1
1=1
and
Σ jm (0% @hit) (stedim aa ti
Wh
kijm
j.j.
(0t
- -Q1a"
kem k. ah kiim
Wh
k.j.m
N
Σ
wh
H.s.mmm No
H +
Σ
wh
1/
No
(V
h+1
V
(5
m
k.j.m
R.m,m, NK.00
i=1
No
+2 2
Σ
Wh
j.j.
11
by.
(54)
N.
For the last term of Equation (54), by (a) of Lemma F.2, we have
No
N
H
H
ba
7
S
NE.
1=1
1=1
Then by Lemma F.6, it holds that
N
Jej Wh
by
H3L
Wh
k.j.m
N (5),
J.j.m k.j.m
k.j.m,
N.d.m,
Hit
Σ
Wh
J.j.
k.j. k.j.m (
T
To<
M] V | Mallllll120
(55)
R.j.m
(sp
oh
Next, we will bound the second term of Equation (54). We can decompose the term into two parts as
T1 Nh
kf of mm)) (Vi - V (5/+11
Wh
i=1
No
Σ k.j.m
j.j.m Wh
Vh+1
(0h+11
(T < < <00] + [ 2 io))
N Di Th
For the first part of the second term in Equation (54), because we have
< 1 by (b) Lemma F.3,
No
(v
- VLL 5' 3' mm' )r DI(0- < (/
h+l (5
kidm ,a J. < io]
h
k.j.
1=1
S
wh
k. 5o
(s an k.dm < in
(56)
k.j.a
46

---

For the second part of the second term in Equation (54), we regroup the summations as follows:
N
Wh
7/
Nh
(Vilf - V/41 (5) /+1
I
N (5/ j. -. ".) 2 in
iml
k
J'm
(Vitzz - Vilit) (5 "m
Wh
(shut1"
(57)
5'm'
where
N
3yh m' Σ I
kimm 0 b.3.m)) 2 60
w/
Mi
No
I [(te (' (K,J', (0,m()]]
kjjm
Let || lo0l max ( and || = Eniim aifiimm Since
No -N 1// S 1 by (b) of
k.j.
Lemma F.3, we have the following property:
|
Σ
whth d'
Σ T TN , ,ah a.d.m) 2 in
wh
k.
S ||W||1,
kt' k/mm i8
R.j.
If we have proved that:
||olooo, S. exp(3//f)lwlllo.))
(58)
then combining the results of Equation (55), Equation (56) and Equation (57) together with Equation (54), we reach
Σ
(0% @hatt) (5 d.m a k.)m Wh
k.j.
kid.m
J'm (V - Vhikk ($ mm)) + H | Woo
k.m. No
Wh
wh 1lo
H
m'm
k.j.
H3, I 10 No- M)
Σ k.jm
k... HI [0 < No < to] +
Σ
Wh
wh
N
k.jm
Σ W J''m m'
wh
J' mld (Q% Q1+41) (5
J'm'
b0, ,441 + v H3S //s/l/llboo 1|
Wh M.j.mmmk......
(59)
k.m.
with || S |Wll and | S exp((3 H|wlloo,,, Here, the last inequality is because
Vi (s V/ of mn) 1 m'mm
H'''m' m' and VLLK' (s"'d" d''''' Z Qh: (5 4
d' m' W K'''m'
With Equation (59), we develop a recursive relationship for the weighted sum of Qh - Q between step h and step + 1. By recursions with regard to h, h + 1,... H, we finish the proof. Proof of Equation (58): Now we have
N
-k' J'm'" mm Wh
Σ 1
[
( a k.s.m) i0 wh
k.j.
11 [(kt
5t fmmmmm (6'j''m')
m
k.j.
1=1
No.
< ||wloook
Σ 1 (
bejm k.im
10
Nk II
[(K' 5'. = (K',''m')
1=1
We only need to prove for any triple (k', m') and any h [H]
( k.j.m
k.j.
Σ
N
[(k* J m²) (K', .n' md)] S exp(3/11). (60)
.ap
20
k.j.m
1=1
47

---

By definition of k', j and m², for any given triple (K',
N
[1kt ,m²) = (K' m')] > 0
if and only if
A.j. ). (bh , ,
(5p
J'm
x mi W < ks and it ('', I ,')) S h K s'm'
where d'(k' m²) is the global visiting number for (6% ,ah is no ambiguity, we will use i' for short. Therefore
W. I mn at (K,m', m') When there
Ng
Σ k.j.m
(
k.mm b.).
No M
[(h' "..,",mm m²) = (W''".'")
Σ k=#+1 j.m
No ( of m'
Ha
m'
2 in, (6 k.i.
an m. = (0h I' mm vf 5'mmm)
-hh (61)
Let k' < ki < 122 < < he S K be all the round index such that ny (sp, L' mm
: o
K 3 mm
> 0 and
No (8/ Obp
m'm m K. md 2 ig for any g E [t]. then we can simplify Equation (61):
No
Σ I (
k.j. 2 k...m)) 2 io
No
[
,,,,,'m' = J,' m')]
k.j.m
Σ J.m
I
Bowim (0
ah
(5
R s''
12 s'. .mm) : 10h
Alp""
No
s' m' Re M' m'm n
(62)
For any q [t] and p 1 1, by (e) of Lemma F.2, the following relationship holds
N I exp(11H).
ne
(63)
tp
Combining Equation (63) with the property (c) of Lemma F.3, for any p E [m]]], we have
N
S exp(1/H)mz
No.
I Eexp(2HH)m)
-p
and thus
Σ Ky H6 m'
nh (5% oa
& mm
S
n
(1)
S
e
Σn nh S cxp(3/H).
8
(64)
g=1p=1
Here (i) is because kn < lg < < S K and N Lemma F.2. Applying this inequality to Equation (62), we complete the proof of Equation (60), and consequently, Equation (58).
Nrt 2 The last inequality by (c) of
Lemma H.4. Under the event ni= Es in Lemma for all e E (0, H), we have the following two
conclusions:
HA
MSAH St
Σ
Σ
TI
[ ,ah k.j.m) - ( k.j. k.j.mn
(8h a
S
2
1=1 k.d.m
and
H
Σ
Σ
Qh: - -1hht
(s
k.j. JI
[ - Q.ar))
(s),
k.j. k.j. > c)
.
1=1 kij.m
1 SAA
<
+ MSAH VT.
E
48

---

Proof. Let N = [loga (H/e)). For any i E IN - 11, k E [K] and given h E [H], let:
k.j. 1l Q (x(())
R.
1 (.. oh dedm)) e, 2'e))
Wh,
and
Jim NN
b.d.mmy I (sh (s) ar
(s (s an
k.d.m [2 H]]
Then
| [wll
max k.j.
S 1, | Wh,
Σ w...
R.j.m
Now for any i E [N], we have the following relationship:
Wh,s i.
(0% -Qi
(5%...m. ah me 2 2" 2 ccllu11..
(65)
R.jm
Combining the results of Lemma H.3 and Equation (65), we have:
H
2 Ellooii 2 v HSSA|lWlli
+ Σ Σ
J.J. Whit
(1) kk
(66)
W= k.j.
where for any h S H1' < H 1,
R.j. (h) = Wh,t
k.j.
Whe
NE
w (h)
E
wH's
a ml (N) a)
i0
NY
I
(k.J.m)]
W.3m mm
Therefore, for any triple (ks j, m) and h S SW'SH
HHS-- H L, we have
Ny
Σ J.jm (h) W111
Σ
Σ
am (h))
I N 2 i0
Σ
NW [KK,,
(k:,j, m]]
Th
Then by mathematical induction on / E [b, H). is straightforward to prove that for any j E [K].
A... < (exp(3/H)) M- 27,
(67)
given Equation (60) and the base case we can derive the following relationship:
N
whis
R.j. ( En Whis
k.j. I 1. Solving Equation (66).
SA
Σnsh Ek.j. Whis
k.j. (h)) y.kjj...
||
(1)
(68)
4'22
2'e
We claim that
Σ
Σ
kkim b
S SMH
(69)
#= k.j.
which will be proved later. Therefore, by
N
I [[(o% - -Ql. (5 o
k.mm R.j.m
2 =
Σ
h,a
k.j.
1=1
we have
H
Σ
Σ
(s k.s.m .a
k.j. R.d.m
(
kamm a
R.j.m 2 c
(4)
(70)
49

---

By Equation (68), it holds that
N
|
h
(
N
SA
N
Σn =i
E j.m
WW
k.m. (
4'62
2'
i=1
SA
N
Σ#
Ek.g.
2'e
1=1
SA
MH*SAVI
(71)
Here, the second inequality is because O S. Wh's ked.n (h) < 27 by Equation (67). The last inequality is because of Equation (69). Combing the results of Equation (70) and Equation (71), we reach
H
H e²
MH
Σ
Σ
k.d.m ,0h ). (sh II [0
K. k.d.m)
S
1= Rm
Now we finish the proof of the first conclusion. Further, noting that
H
Σ
(Øh - o1:²))
(5% oh
R.j. M.sm y [ - 01/²))
($% ab
k.j. R.j.
2
H
N
2'elwolli.
2'
-=1==1
SA
H
H
Σ
N
R.j.
(h)) )
youi
Whi
2'
1=1 N
k.j.m
SA.
H
k.m
6
1=1 1 R.j.m
SA.
+ SM
Here, the second inequality is by Equation (68). The second last inequality is by Equation (67), and the last inequality is because of Equation (69). Next, we only need to prove Equation (69).
Proof of Equation (69): By definition of x k. we have the following equation
No
No. H
H
Σ T[0 < N < <))
Σ k.J.m
H W
[0 < No < <M. (72)
k.j.m
k.J.
k.j.
For the first term of Equation (72), we have
Σ
no No
NW Σ Σ (N = 0, (s .04
k.j.
k.jmm = (s, S MHSA (73)
Reg.om
8.0 Nigion
The last inequality is because if we let ko(s,a) a) be the round index such that N (s, a) 0 and N/ +1 as) > O, then by (a) of Lemma F.1, it holds that (s, (s, = O, (s
k.j.m an
k.j.m (8, = No (s, a) S M.
k.
Let ki a) max(k 1 N () < io). Then for the second term of Equation (72)
Σ Hul 0
No
( .ap ......m < <10]
k.j.m
H
Σ
1 10 <
(s, < io (5 k.i.
, a.a.m = [s)
8,0 J.j.
kn
H
(5 a. : ck.5.om = (s. = HHH >
k.j.om
MHASA (74)
8,0 k=1 j.m
8.a
50

---

: (s, a) - 2M by (a) of Lemma F.1. Here, the last inequality is because Nº (s, < do and thus n Finally, for the last term of Equation (72), by Equation (24) with a 1/2 and wh kdam 1, we have
H
NE (5
an a.g. M S 22MFHSSAVL
(75)
No.
k.j.
By applying Equation (73), Equation (74) and Equation (75) to Equation (72), we finish the proof.
In the next lemma, we will bound the difference between V/R..((s) and (s). Lemma H.S. Under ni & in Lemma G.I, it holds for any (s, h, k) S x [H] x [K] that:
0 S VR (s) (8) S B.
Proof. If for any & E [K + 1), (s) (s) B, then according to the update rule of the reference function in Algorithm 1, we know RR (x)(s) = O.
Otherwise we can assume that there exists & E [K + 1] such that (i - v (s) - B. Define
k1 min V/ (s) h
11. (s) S B).
Then for any & < 11, it holds that (s) V/-n (s) B and thus Viilk
k (s) 0.
We claim that un R. (s) True. If un (s) False, then there exists ko ki 1 such that u4 R.Ao- (..
(ss = True and u/ R. (s) = False Based on the update rule of the reference function, in this case, have ViA (s) k. (s) -) S B, which is contradictory the minimality of k1-
Since VA (8) Vhiki (s) and R.A. 1 (s)
un
True, we know for any k 2 ki,
VR (s) V (s) Vi (8) S v/. (s) 3 (s) + B < V (5) + B. The last two inequalities are because Vi (s) S (s) S V/ (s) by Lemma H.2 and Lemma H.1. For any k 2 k1, we also have VRR.A (s) = Vi Ri (s) = V (s) 2 V/((s) and thus finish the proof. O
Lemma H.6. Under the event N E, in Lemma G.1. for any (s, k)) 8 x [H] [K], we have the following two conclusions:
1 V.LK (s) S B, then Vh+1
v.R.K+l(s) (s) V.Rk (s) (.R.(()))
(s) wLik (8) B. then have:
0 S W (s) - (.. IV - h+1
(R.K+I(s)) (s)] S Vi++(() V (s).
Proof.
If for given & [K], V (s) V (s) S 3, then there exists d E [K] such that:
k min { k: V (s) v2 S $]
Then according the analysis in Lemma H.5, we have R.A1-1 (s) True, or it contradictory to the minimality of Kj. Therefore, in this case, we have:
w
vR,++1/
(s) = viRk (s) = h+1
yR h+1 (s) = (s) I VL. (s) + 3 5 (s) + B,
and
RRA (8) V A+1
(R (s) Vhy (s) (s).
According the definition of V.R.K (s), we have V.R.A ( VR (s)
vRK+I(s))
h+1
Moreover, if V
v (s) VILk ( > 8, according to the algorithm, we have VR, (s) and then 0 < V.R. (s) - b+l (s) - (s) - h+t (s)
In this case, we also have vLL (s) S (s) S V.R.K+((s) (s) V.R (s) and
then Vi (s) S Vir V.R (s) < (R((()) (s). These two inequalities imply
that /RR. (s) FR,K+ (s)) < VA (s) (s).
51

---

I Proof of the Worst-Case Regret (Theorem 4.1 and Theorem 4.3)
I.1 Proof Sketch
In this section, we bound the worst-case regret under the event n & in Lemma G.I.
For h E {H + 11. denote:
M
M
6
V
VT+) (s )) ch
Vh Vx²²) (s) J...
1=1 m=l
Here, 0//+1 = + = 0. Because (y)()) = sup,, Vi, we have 8% < Sh for any h E [H + 1]. In
addition, as V/ 2 (s) for all (s, k) E S x [M] x [K], according to Lemma H.I, we have:
Regret(T)=
Σ (vit(sfdli)) - 1/= (5 (s/tdmm)
(v+(s)).i)) - v/=" (sf.dm)) Σ S
k.ji
k=1
Thus, we only need to bound Σk=1 ct.
K
Σ (0%
Q (8h k.j.m . .....mm
k=
k.j.
Σ (hh (5 km an d
Σ (Q% Q% (6hhimm di
k.j.m
k.j.m
( (s
k.d. .a
+
Σ P p..m aa aa , (ii+1 - v (76)
k.j.m
A.j.
In the last inequality, we use 0% a) S Qhaa(ss a) and Equation (1):
(s,
()) = as) + Ps Vi+1 Q% (s. = (s, + Peea Vh+t1
Next, we will bound the first term of Equation (76). Back to Equation (52), since D-R we have the following relationship (Here we use the shorthand P = P k.a.m kudoo
R.
h+1 S
h+1
(Q
k.j.m an
k.j.
N
No
No. H +
No m/
(IVif1 -V (5/41 + R - -PV + Σ
8" fm
Na BR
S
17
T/n
x=1
n=1
N
N
11
N
H
+
Un
No
((hht
[5 + 14
k" _m=
R, - PVi+.))
+ Σ
Tn
Na
hmn
(77)
==1
1
n=1
and thus
Σ R k.j.m
(5 pm a k.
N
N
Nou
No
H
Σ
Th
N
(1Vh V.RA" ) (shit) + pn
5"m""
R1
FVi++1)
+
Un
Na
11.10
k.j.m
R.2 H22
<
110
N
H
+
Σ
(R.l (olii , .a k.j. + 20,
N
k.j.m
k.j.m,Ntto
Σ
No
(Viti
V ("m"
mm
k.j.m, >on=1
N
Σ
Σ
mm
((Vi41 - (.R.A")
k" 3rth mm
+ +1h
R
P. Ji 2. J Viti)- (78)
Nt
52

---

The last inequality is because
No
R.2
No H2,
R.2 H2, +
7n
S f%
R
+2
R.2
(79)
n
N
by Equation (53) and (a) of Lemma F.2. For the first term of Equation (78), similar to Equation (73), we have
1l
N
H=
Σ UNz
0, (sh an
RJ.m " (s, S MHSA.
(80)
5,0 K.j.on
For the second term of Equation (78), by Lemma F6, it holds that
R22 H
Σ
2ch
S 2c, R.2 M + 26, 22222222 S
(81)
N
N. 20
For the third term of Equation (78), similar to the proof of [113, Equation (25)), it holds that
Σ
Σ
No Mm
(V
(i+t) j""m"""" S exp
3 H
Σ
h + 2M
(82)
K =0
Taking the above results Equation (80), Equation (81) and Equation (82) together with Equation (78). we can rearrange terms Equation (76) reach
K
K
3
t1 + (2c5 + 3) SA + 2 S2
exp
H
k=1
k=1
N
Σ
Σ
mm
N
(
h+1 ( "m""
(8/+1
Mh
RK
P k.s.
k.lm n V
k.j.m. >on=1
P
k.p.m a k.s. &o
(Viti -v7tt)
Σ
( (s
a
k.j.
k.j.m
N.J.m.Nk.s >0
K
< exx
3
Sh+1
kk
(2 +3)MHHSA 20 2
H
k=1
N
Σ
mn
No
1 am hol
IP kijim .a,
k.s.m.))) (1) (Vi V.R.A"
N Son=1
N
N
Σ
VRR kf
gesm R.sm N R.
Tn
(8h+1
k.j.m, No Son=l
1=1
P
(Vitz
Vitt1)
Σ
RR ( (s .0 N.simm).
a
k.j.m
By recursion on h, since shr+1 O. we can get the following conclusion:
Regret(T) <
s < MH + Rí + Ro R3 Rs,
where
H
R
Ph (s
R.R Jegio Aa..i
aa
h=1
k.j.
H
N
Rg
Σ
CH
Σ
Σ
Nk
(1
arsi aat.s. s.....m.) a.) (Vzti 12R
k.j.m, No
>0
53

---

NE
N
R3
H
In
N
(Ve (5/-1 oh son
m' - PP a.mm in d h+1
F.R."
h=1
Ki N n=1
R4
Σ
k.di d 1 (..)
(Vitz Viita)
and eи = H)) Under the event &5 in Lemma G.I, we can bound Ra by 27 27V2H2T11 Then, reach
(Tg S V H MH + R + R2 + Rg.
By Lemma 1.1, Lemma 1.2 and Lemma 1.3, have:
Regret(T) & (1+ B)V HPSAR + 1 S1
SH2.
By (b) of Lemma F.1, we have
log (2SAT]
2SAT
2MHSA
MSSA
0
log
log
=0 log
Let 5/14 and = log
MSAT p
then with probability at least we have
Regret(T) $ 0 (1+ B) / - S MH
The proof also holds for M- = 1.
1.2 Upper bounds of R1, R2, R3
Lemma 1.1.
Under the event T & Lemma G.I, 1, we have
R1 S (1 + B) HPSTTIL
V HT' MH*
T [
Proof. Since Bh (s) ( k.dm kJmm
a. 2 0, we have
R1 x Σ
( R.di keimm
On
h=1 Jej.m, N
H
Σ Σ
VIOR R.R. (1B.t122) v H (o (1()tee))
(83)
V
V
h=1
k.j.m,Nt20
For the second term, we make the observation that
(M A k.j. k.j.m) (
A.k
A
No Tm
(Vrer,
R,K" jn h+l (s
S
h
SB NE
(84)
(. app
NE
N
The last inequality is because 0 R,
h-1 S B by Lemma H.5 and
N N
by (b) of
Lemma F.3. Therefore, we can bound the second term by Lemma F.6 with w/
k.m.j = and a 2
H
Σ
A.k
(4 (3
oh
N
k.j.m. N >0
H
B
NE
Aml N.j.m. 20
S BMHHSSAL+ B SASA
BV
(8.5)
54

---

Next, we will bound the first term of Equation (83). Since v 2 V (s), we have
R.
(1h
R.k
jk. + Jk..
h
(86)
(8 a. a....mm
N (S k.J. aiim
where:
E m=
(RRA"
(DR."" (s
1" mi)
jk.j
h+1
m=
1,h
(5 Oh a..
(6 k.j.
on k.
and
N Σ
R. " "ammmm"))) ))))²
(8h41
N R. (s "m"" n=
jk.j
(s aa med.m)
N (s Oh k.s.m)
Ridim
Now we want bound both jkm and J. Note that
N (VR + V.R.A"
(VR RR, kn
h+1 ) (s/++1
.9h (5
N... k.J.m))
2H (.mm
(87)
NK Neaim
where
(
k.j.m Oh
(VR. "m""""" D.R.K" (o (8/+1
h+1 (6 "m"))
(88)
For the second term
2
because of Cauchy's Inequality, have:
Ein Dial (s mmm N N6 "a "
D.R." A0 ""mm" h+l
(8/41
j.m
2
(5
kijim .hp m.
jojm pk.j.mm m
2
2,h.1 2,h,2
where:
2
(Vits F.l. (o
Ena
Vitta) (vRR h+1
(s 3" mm)
No J.m 2im
jkjm
21h.1
( k.t.m k.j.mn)
and
2
Σne NO
(iita (A"" mm)
Vieu (ofe oe montt
(o m.
12
N/ (ot aa mm
N
V
k" mm")
N Vis (m sm m h+l
2
h+1
Nk (S
km k.j.
.0p
(f a.
Since (s) S
N44 (s) S Vinni
+ B, holds that:
h+1 - Vittt) (sA"15" """
(Viti
D.R of imm
h+1
(8/
(s
k.j. aa k.J.mm)
No Σ
(ii+i h+1
(s 5 mm
(DRRe" Virti 3
NK km aaa km
S 233
55

---

Jk.. Therefore, applying this inequality to 2,6,1 we have Jkj.m
2,h,11 I 4.32.
Moreover, we claim that:
J.jan 2,h.2
S S.V.k V....m a (Vi+1) + H²
(89)
V (o (o aa mm
This is because (Here we the shorthand IP = IP siisim sid. mn .a
j.j. 2.h
V Vakcim Kadion (Vh+1)
En
3m - -P) (Vitt.1)
En Vitta (" "m
Sh41
+ (PVV++1)*=
(6 a
k.j.m m
No. (5% -
k.jin k.j.my
ΣN No
1 am - PP) (Viita2
En
gm - P) Vi+t1
Sh4l
+ 2H
sh41
kddm m.)
(5
kitm km
,,a
S H
(6 Oh k.immy
The last inequality is because of the events &g and & in Lemma G.1. Applying results of Equation (87) and Equation (89) with 2,h < 4,3² to Equation (86), reach
h
R.K
P4
R.A
H k..m k.jmm oo
ki .a akei. (Vin1)
k.Jm a.... Nà
(8
a
NA. k.j.
( -h
k.m. mm
32
H
(90)
V
(N k.mm a 1)
a
Note that by Lemma F.6 with and 3. we have
32
Σ
S BMHSA++ BV / HSAT,
(s (aai a k.)
1=1 k.j.m. >o
and
H A.j. on
Σ
E
& MH'SAA (T))))
(5
k.j.
k=
Applying these two inequalities to Equation (90), it holds that
R.K O
R.R 14h
Σ
Σ
A.m. k.S.m ,a
k.j.m.
No.00
( k.jm
k.j..yy .a
H
V k.s kam l Wit
( ,a k....m)
(s . s.
4=1 N
M + ( By HSAT.
(91)
Now we claim the following two conclusions
sy a Ass n (Vit1)
bism
Σ
HHSAA MH
(92)
(5 kilm R.din
k.
,a,
56

---

and
H
(iam k.a.n) ,aa :0
/ Ht's SA MH
Σ Σ
(93)
k...m.ff0
which will be proved later. Combining the results of Equation (85), Equation (91), Equation (92) and Equation (93), we have
R1 S (1 (1+B)) + (A((S)) I
VI +
MH
2 3IV HSSATI
H' MH
SA by AM-GM inequality. The last inequality is because (T) < + Next, will prove Equation (92) and Equation (93).
Proof of Equation (92):
Because of Equation (23) and Equation (29) with w/t A.jm 1, 1. we know
(s
k.j. k.jm = (s) an
M + VNx (
(94)
N.J.m.NAoo
(s.a)
Then we can derive the following relationship
V Aim on bism (Vitz)
(5 k. -a k.
R. No
50
V (aan(Vitt)) (8,
Σ Σ
k.jm d.bmy = (8,
(5p
h= 8.0 k.j.m.Nkk0
(Van(Vitt))
[M+ (N
1=1 8.0
H
< SH
(s,
hml
S MH HSA
Σ
V.s. a 5amm (Vitz)-
(95)
K.j.m
The first inequality is because of Equation (94). The second inequality is by Va S H² The last inequality by the Cauchy-Schware inequality. Next, we will bound the term in Equation (95).
H
Σ
Σ
Juso aa badan h (Vi+t))
1=1 k.j.
H
H
Rosto kison A (Vitz)
kidm k.d. (Viit)
Nesio ksm J. (V
an
h=1 k.j.m
k.j.m
H Σ
$ HT + 3
kidim aa kamm Mo (Vi+t) W k.a. . tmm p.
(Vork (h+1)
(96)
k.j.m
57

---

The last inequality follows directly from Es in Lemma G.1. The second term on the right-hand side of Equation (96) can be bounded as follows (Here we use the shorthand s o 2... ,
Kamm kas. A (Vi+1)) 8h
kusm fusi A (Vi+t))
(PVi+t1²² + (PVV711))
1=1 k.j.a
11
Σ
P - Vo - (
(Vi+i
+ vati)) + |(PV (PVVitz) }
1= J.j.
H
< 4H
P Vitt1 -vitt)
h=1 1 k.j.m
4H
(
Vi k.5.mm) + (P- 1P-1,14 ) (Vit+ - vata)}
(
R.J.m
H
VuL h+1
Vitti
(m)))) + H² Ti
1=1 Aajmm
25 H'V M
(97)
Here, (i) is because VI4 2 V 2 Vit+1 by Lemma H.1 and the event &g in Lemma G.I. (ii) follows the event Egg Lemma G.I. Therefore, applying Equation (97) to Equation (96), we reach
Σ
kalm k. a (Vi+1) HT + M SA
(98)
k.j.m
Here we use H$ H* I HT1 + MH SA by AM-GM inequality. Applying Equation (98) to Equation (95), we finish the proof of Equation (92):
an N.mi s.m Ja (Vi+1)
MH VHSA HT, + MH'SA
NK J.m . b
K.j.m.Nkso 30
H'SAT + MH
Proof of Equation (93):
First, by Equation (24) with wA A..m = I and a = 1/2 and Equation (32), we know
K n a)
T [0 < (s, < M] S MSA.
(99)
(s.
5.0
a)
(N M]
< log(Ti).
(100)
(s
Because (x) S (s, a). it holds that
Σ
#
Σ
( k.im kijm
,ah
I [0 < ( ( < M
(8
k.mm k.m.
h=1
&. >0
11
()(s,)) a) I < Nh(o,a) <M M MH'SA
(101)
(s)
1=1 8,0
58

---

The last inequality is because of Equation (99). By Equation (100), We also have
H
V (6
K..m k.j. k.j aa ah m)
Σ
Σ
(s oh s. 2 M
HH (s)
(h. M, (5 ( oh c.. (s,
k.J.m. >0
H
K HI (s
(s,
(s, 2 M]
())
1=1 8,0
(Ti)
(s,a)
H1
SAH2
w (s.
(102)
A=1
8,0
Here, the first inequality is because of the monotonically increasing property of (s, a) with respect (see its definition in Equation (88) as guaranteed by V/R (s) 2 R. (s). The last inequality by the Cauchy-Schwarz -Scwwaz inequality. To continue, by Lemma H.6, we reach
H
Σ
W (8,a)
H
VRR
(R.
h+1
h+1
11
k.j.m
H
Vh++1 - 1+11
(s I [V - Virlt (s > 3)
1=1 k.
H
1 Qh++ - Qlitz)
Rui. d [(o
- 21:ti (0h+11 aa.111 > 3)
h=1 J.jma
SA.
B MH.SAVL.
(103)
Here, (i) is because
k.j. k.j.m) V (s")) k.j.m Qh+n (5h A41
a I V.Lk V
The last inequality is by Lemma H.4.
By applying Equation (103) to Equation (102), and combining the result of Equation (101), we complete the proof of Equation (93).
Lemma 1.2. Under the event 0
[1 & Lemma G.I. I, we have
14
R2 S B.//B/HHHH HHSAATL + MH
Proof. By event E1 in Lemma G.1, we have
H
3H
R₂ R 2
Σ
Σ
Σ
N
N
hm j.mm >0
h=1 k.j.m.N
$ H / (SSAT) + + HSA)
S 3 HSSAT + &
The second inequality is by Lemma F6 with 1/2 and a = 1,
59

---

Lemma 1.3. Under the event N==1 & in Lemma G.I, we have
+ SAS
R3 x (1+ 8) 3) H
SA. 3 + S
Proof. We can decompose Rg into five terms:
N
N
R3
Σ
(vr (vRi m3
(sh+1
IP k.J. k.t. n A+1
V R.A.
V.
N
+1
on .0h
R3,11 + R3,2
R3,3 R3,1 R3,5
where
N
No 41
Ra,1
Σ
CH
Σ
In
P k.s. Preai .0 km nn
(V/ V(+1):
h=1 1
k.J.m. >on=1
H
R3,2
Σ
1 Leggtmm IP c.s.m ,aa
k.diin 1b) Va+ii
Nk=+1
h=1
N.j.m.N >0n=1
1=1
N
NA
R3.3
h-1
Σ
Un
N
Witl (5/41)
(e....mm) DR, kt mm))
(s/4t)
No
k.j.m,, N=
N
H
R3,1
CH
h-1
Σ
No
Paim fmsm % a
h
(DRA
h+1
VR.K+1)
h=1
k.d.m.
and
N
R3.5 Σ
Σ
No
VRRKK-
D.R,K"
Un
k. a
kam &o
h+1
h+1
h=1
N.j.m, N S R=1
Next, we will bound these five terms respectively: Upper bound of R3,1
According to the event E in Lemma G.I, we know
N N1
Paysim aammaahiimm s. )
7n
Σ
h+1
Vitta)
1=1
Bijm
N
/2i
N
h1+1
B
N
1/2
No
(ii)
3
(104)
N
N Here, (i) is because 7he k... (ii) directly follows (a) in Lemma F22 with a J. Therefore, by Lemma F.6 with 1
exp(1/ H)) N% by (c) of Lemma F.3 and N > by the definition of
Ra.1 S BVT
Σ
Σ
B 3 HSAT
(105)
1=1 N.j.m.ks
N
60

---

Upper bound of R3,2
According to the event E13 in Lemma G.1, we know
N
41
Th
IP dedii s4
Vi+t1
1=1
N
kaion ah aa n nVViit1e
N
7He
Tn
N h
No.
ev
N Tim
N
JJn
N
uidi Aimi (iitiie d + Hi
vn
Y2
n=1
n=1
V
poli aa k.s. WVita)e A/
H N
(106)
N
< exp(1/HH H) N by (c) of Lemma F.3, N N 2 n by the definition ka (ii) directly follows (a) Lemma F22 with a and a 1. Then according to the definition of R3,2, we have
.2k Here, (i) is because 7n
k.j.m k. k.mm
H
Ra
Σ
Σ
(107)
N
N
1=
N/
h=1 N.i.m,N,00
For the first term in Equation (112), by Cauchy- Schwwar inequality, we have
kaam (V+ 1e
kaiim aa
N h
1=1 l.j. A.J.m..K NN >0
Jidii an tism 1)
(I No M + 2 M))
No.
H
II [ < N < M
Σ
k.d. k.m. (Vi [0 < No. < M]
N
h= k.j.
h= k.j.m
[ 2 M]
H
oy bimm a k.mm (Vi+ [N M]
N
A=1kj.m
k.j.m
" H Σ II /= k.j.m
S MHSA
< M
VHSA
(108)
Here, the last incquality is because V k.d. k.j.m (Vi+1) & H2
H
1
No M
" S MHSA,
Nk M
S HSAL
N
A=1 k.j.m
1= k.j.m
by Equation (24) and Equation (32), and
(Vi+1) S HT, + MH SA.
kaam k.m
k.j.m
61

---

by Equation (98). Next, we will bound the term Σ Im. I 10 < N < <M. Let ko(s,
max(k 1 - K, (s, a) M). Then it holds that
Σ Σ
I M]
h= j.jm
ΣΣΣ
1 0 (s, < M, (s 24 dedm = (8,
h= 8,0 R.
ka(=.))
kjjm (.d.m) (s,
(sh on
No. +1 (s MHSA
(109)
hm
The last inequality because N (s. I M and ni (s, a) < M by (a) of Lemma F.1. Applying this inequality to Equation (108), we can bound the first term in Equation (107):
H
V komm kkmm A (Vitt)e
Σ
Σ
Σ
S / HRRAATI + S
(110)
h=1
k.j.m,N
For the second term in Equation (107), according to Lemma F.6 with a we reach
H
H Σ Σ
1 MH + H & MH*SA..
(111)
NE
1=1 k...m,N
Applying the results of Equation (110) and Equation (111) to Equation (107), we can bound R3.2:
Ra,2 S / & + MH'SA."
(112)
Upper bound of R3,3 and R3,4:
We first substitute the terms (Vit1 RR A' of' mm in R8.3 or IP p..... a.....a...... h+1 (5/
VRR
VR
RRK+1
h+1
h+1
in Ra,4 by Wk h+1 (8% on k.im)) and deal with the following general structure:
kiim
H
N
11
Σ
Σ
Wh (s)
.a .a k.s.m)
+1
R.j.m,, N >0
Here, S Wk' R..m ,ah (6
A.mm kij. < H because H 2 R.K. 1e mmm)) RR I'mmm
(b .mm).. Since
(5h+1
wi ( m. a
k.j.my S and Ex Tm
_ < 1 by (b) Lemma F.3, we first note that when
O Nk (5h aap
kamm k.jm < M.
N
Σ CH
On h
Σ
We Wh- W
(skd..m a, A..." [o [=< N < <M]
R.j.m n=1
HI <M
H
7/
N
k.j.m n=1
Σ HI < N < M & MH.SA.
(113)
k.j.m
62

---

The last inequality is by Equation (109). Next, we consider the case when Nox (s : -0 aaf.imy 2 M:
H
N
11
1
Whil (8%. km
% - N 2 M]
H
M
N
j. n=1
H
Σ
Σ
W h- (5
h=1 We J'm
N 11 11
I 2 M
CH h-1
Σ
I [K, m'm) - (K (,'mmm))
(114)
No
By the definitions of kf, j and m², for any given triple (K' J', m').
N +1
[[ J", m') (K,5', m²)
if and only if
(m.... 0 k.
K' J'm'm an
I'm' and Noth 2 1' (K', ('' m').
a
where ''(K.'' m²) is the global visiting number for (s &' m' K "f' m'm h)) at (k', m²) with the
order "round first, episode second, agent third". When there is no ambiguity, we will use for short. Therefore, for the coefficient of Whi k.d.m k.m. in Equation (114), we can derive the following upper bound:
h+1 (5% ,
N -
I [ 2
M
Σ
I
= (K,
nn
No 41+
k.J.m n=l
N
CH
Σ
I (s
k.j.
. k. = (s 5'mm &. aml ), No 2 M1
Oh
Σ
fn
h
No
+1
kidim
n
Σ
, an b. = (sh Mo
.m K
m N 2 M) No.
k.m.m
K
n (s) m'm K. I Smm)
On
(s
I' mm
x 5' mm
2 M1
(K j'j' 1 s'
2
(115)
Here, (i) because
N TTm
N
+1
n
N
1/m No by (c) of Lemma F3 and the last inequal- ity is by (a) of Lemma F.2. (ii) is because of Equation (32). When the coefficient of
.
where the first inequality is because fj
<
WK (s k.m.m ah df... in Equation (114) is non-zero we have (st.s. ,a a... = (s I'' m' K J" mna)
and thus We' (s) k.j.
.a% k...m) = WK' Whi1 (8)
H I'mm o &''m") Therefore, by applying Equation (115)
to Equation (114), we know that
NA7
H
No
whld ( (s... k.j. a (.J. | 2 M]
Th
N
1=1
kej.m n=1
WH (5 H.d m'
K S'm'
(116)
1=1 &. mm
63

---

Next, we will bound the term Σm=1 Ens. Whe h++ (s :0 .. By Lemma H.6, we have
H
Σ
V.Rk (1 (.)
R.
($/+1) k.sim)
Amm mm
(V (5 (5 )) ( (1 Viiti (s > $)
R.j.m
Σ (oh+1 ( #+1 "
(0h+ (
Auju ( 8)
1= R.j.m
St. SAVE.
28
(117)
Here, (i) because
@ha1 k.m kdd.))
VAL (o
kdd. ( S V (s/tt1))
9441
The last inequality is by Lemma H.4. Similarly, by Lemma H.6, we also have
H
V.R.K
ki k.mm Je
A+1
A=1 kmj.m
kem { {(1it ( k (x - (s > $1}
P. jei a
k.jan
(V142 ( V (5
v Vhti (ottrr)))))))) > B] Hi
1= k.jan
(oh+n -
Ohtt1) (s
Audum ) [ - (5
kdm. kJmm > 3) + Hi
1=1 R.j.
HOSA
+ SA.L
(118)
B
Here, (i) is because of the event ε of Lemma G.I. Combining the results of Equation (117) and Equation (118), we conclude that
H
HA
Wh ( a
J.m. k.
S
MH.SALL
B
1==1 K.g.on
Back to Equation (116), we have the following conclusion:
N
Σ
Th
Whl
(5
&.J.
| M
N
H SA?
MH
Together with Equation (113), we reach that:
S
Σ
Whir kiim k.s.m S
+ M SAA (119)
H
3
1=1
k.j.m, NKSO
1=1
Therefore, we can bound R3,3, Ra.4:
SA2
R3,3, R3,4 S
+ MH2
(120)
3
64

---

Upper bound of R3,5
H
N
R3,5
Σ
H
h-1
Σ
P k.m. pamm
l+11
V.R.AA")
h+1
hml
R.J.m,N g 20 n=1
H
N
Σ
V-R,A"
H
nn
a.sm mmm
h+1
h=1
R = sonm!
Since
|RRK+1 (s)
h+1
V (s) S and Σ
No En
I Njm
by (b) of Lemma F.3, we first note that
when
0 < (5 Oh
j.
k.j.m) < io.
H
No
H
Nk
k..m a kimm h
h+1
D.R.k" 4+1
I < No < iol
h=1
R.j.m n=1
[0 N < <io]
h=1 k.j.m
SS.
(121)
The last inequality is because
Σ Ni<NN*s77 (idm o A.Sm) < S MA
(
(122)
k.j.m
by Equation (74). When N ( a
k.J.m)) 2 io. have:
No Th
kesi aa k.s. n VRRK+1
R h+1
11 [ 2 00]
k.J.m
v8,K+
F.R.K/
P
kimm J.d.m %h
1=1 R'''m mmm
N
h-1
Ja [
2 to] I[(K",j" mnmm"m = 5" ,3'',mm'))
CH
k.J.mn n=1
P Ff in In 6k
|RRK+1 R.
1=1 k R'.j'.m an
1
+ SH.SAVL
(123)
8
The first inequality is by Equation (60) and the last inequality is because of Equation (118). Together with Equation (121), we can bound Ry.s:
R3,5
H
NE Tm
k.j. k.
RR.++
h+1
RR
h+1
h=1
k.j.m,Nk
>0
Hd SAt
<
+ MH'SAVL.
(124)
B
Combining Equations (105), (112), (120) and (124), since 3 < H, can bound R3:
R3 S (1+ 3) H + S M SA.
65

---

J Proof of Worst-Case SwicchiggCommmuication Cost (Theorem 4.2 and Theorem 4.4)
Proof. We first prove the Theorem 4.4. When T= T/ (H + 115A, the number of rounds k is more than T 3M + 1)S A. Next, we consider the case when T 2 3/12 1)SA.
Since each round terminates when some triple (s, a, h) satisfies the trigger condition (see Equa- tion (3)), the total number of communication rounds is upper bounded by the total number of times the trigger condition satisfied across all triples (s, a, ht.. In the following proof, we provide an upper bound on the total number of such trigger events.
Let (s, a) denote the number of times the trigger condition satisfied by the triple (s, a, h). According to Equation (3), each time the trigger condition is satisfied during any round k, the number of visits to (s, h)) increases by at least when N (H(H + 1) _ 1/6- and increases by at least a factor of + 2MH(H++) when No 2 %-- Define the set C = {(s, a. h) (x, 2 %b- Then for every (s, a, h) E C, after the trigger condition has been satisfied i times, the number of visits to (s, h) is at least i/. Therefore, for (s,a, E C, we have:
(n(aa)--15 16 -
N (s,
(1+ (
%
and thus
log(N Dog(Nt+ (s, (s, (8.a)/%)
K
())
+ t.
log + 2MH(H+1)
If C 0, then
ΣΣ (s) Σ an)
HSA S MH 1)8A.
(e,0,h)fC
Otherwise, the total number of trigger times is no more than
Σ an(s,a)= Σ (n(s,a) +
Σ (s,
1=1
(s.a)ec
(s.0,))EC
log(N K (s, as)a)/io)
$ + +
Σ
(s.a,)Eee log (1 2MH(H+I)
log( M|(H+
S + |C|
+
log (1 2MH(H+1)
log H1HH+188A
s (H + HSA
HSA
log 2MH(H+T)
T
< 2MH + 1)SA+ 4MH (H + 1)5
H2 +1SAA/ )
The first inequality is because for (s, a, h1) $ C. (s, < 1 The second inequality follows from Jensen's 's inequality. The second last inequality is because the term in the previous line increases with [C] when T 2 ( A and < [C| S HSA. The last inequality because log(1 z/2 for x E (0, 1), which applies to 2M
For M = 1, the switching cost is no more than the number of communication rounds. Then we also finish the proof of Theorem 4.2.
K Proof of Gap-Dependent Regret (Theorem 4.5 and Theorem 4.8)
K.1 Proof Sketch
We now prove the gap-dependent regret upper bound under the event 0 E, in Lemma G.I.
66

---

To begin, we point out that
V/2 - v4a (s7.d-m)-
= 1/2 (5) (5 A.d.m al a.smmm + (Qi Q7 (sfid.m, al am
As kuj.m aj me) + E ( V/2 v/²) (8h-).mm) k.m Pi (-1 st.d.m , af..mm)
E
A (8) k.j.m a1 m. + (2 km
a2 (....rn)
w. P. 81
k.j. a1 A...m.))
E
(03 Q3") (52
1... d2 )
k.j 82
P1(- $1
ai )
H
E
An
k.i.
a
k.s.m
k.jm 8h+1
Px
an "..."), [H -11 11
Here (i) is by the Bellman Equation and Bellman Optimality Equation (I). Therefore, we can derive the following expression of the expected regret
E (Regret 7)) = E Σ
vTt) (st.dim) = (vi
kidm k.J.m Au (5) o4
k.j.
kig.m k=1
Note that we have 2h @ a% (.)) max (aax(Q((ss (5 k. .))]...a)))))))..)3) 2 max (5 J. .a)} Via (s)
Thus, if we define clip|æ []] = x- 1|x 2 vl. then for any round-step pair (k, li),
An k.j. an k.d.m clip Vi (sh (.J... (1 (5 a
k.J.m)
min
clip
[ Q%) (m . k Amin]
which further implies
H1
E (Regret(TT) S E
Σ Σ clip [0o - Q%) (sh k...m chsimm)
Amin)
1h k.j.
Let E = M & and 8 = -1/14T,, we have:
"
clip [00 QQ)) (sh
E (Regret(T))
S EE
k.j. k... A min E P(E)
du
1=1 k.j.a
If
+ E
clip (0th -Gh) (s
k.i.
,0 aheiiim Amin
ge P(E))
h=1 k.j.m
(Q* + H) SA.
H'SA2
0
MH
Amin
The last inequality is because under the event E, by Lemma K.2, we have
clip [10] - Q7) (shadim a
Jom.m k.j.m)
A min
h=1 k.j.m
(Q + 3H S
+ +MH*SA?)
A min
B
and under the event E", we have
"
Σ Σ clip (00 - (1)
k.im
,a
R.j.m
Amin < HT.
1=1 j.
Since ATg /8) A2) by (b) of Lemma F.I, we have i S O (lSg(M))T))
Therefore, let 12 = log (MT)), we have
(Q"
3 H) S
H'
E (R) 00
+ B + M SAL
A Amia
67

---

K.2 Auxiliary Lemmas
Lemma K.1. Under the event Ni=1 & in Lemma G.I. for EeelySSrttee--Loweee algorithm and any non-negative weight sequence (whh j. it holds for any [H] that:
Σ
k.j. (Qh -5h kmm ah k.m 2 H. / (Q' +BHH)) A.B.tt)sAlllllo...llllll. 1,0
Wh
k.j.n
H
+ (SA| (IW]ll..))
+
Σ
wh (h) Ziegimm
where for any h S S H 1
k.j.m (h) == w/h k.j.
Wh
N²
k.j.mm (b) wh4+1
Σ
wh S. mn (1i) NWW 2 i0 Σ
NW. ((","'m') = (k, m)]
7/2
W me
1=1
and
H2L +
H
No.
=170 H +
+ +1110 < No < iol
No
10' + 32
H
[ < No.- < M
N
)
N
Th
(IV
V
k² ,3' .m ($11+1
)+ + P pa agg wo (VR44 vR447)
(125)
+1
Here NN.NE No. is the abbreviation for No. ($
K m' s'
) (s
R.j. and. respectively.
Proof. To begin with, since 2% (s ah k.j.m S Qhi (s/ o d. by Equation (77), we have (Here we use the shorthand P F A:si oof mn
k.j.
(Qh
(s
k.j. on k. < (2 (s) anp k.
N
N
No S 17u
H +
.N Ta
((Vh")
himl (sp+1 Mh
""""","""
.mn"
RI
PVi+1))
Mn
Nº
nn (126)
No
R.2 H2,
S 170
No H +
gR.k + 2ch
7m
h (Vh"*,
V /+1
No
xt
N
No N
Noè 11 kijm - P) (Vi+11
V.R.A
+ Σ
1 (Iggghime
PP) -P) Vi+ti
In
N
+T
n=1
n= 1
1=1
Ng
7/n
h
No
1 Legg pP)
(DRRAF
1+11
Vit
n=1
NA
N2
(VVRA'
mmmt ) + PP (V (441) v2A4))
7m
(s
(127)
N
The last inequality is by Equation (79). In the last inequality, we decompose the second term in Equation (126) into the last five terms in Equation (127). We then claim the following five conclusions:
NY
Σ
Im (V
V (5 5" .m II No < to] s HI < N < <i]]
68

---

( (s
aa
k
S B
Nox
H
+
V
(O+ + g3)e
No.
(Ng)
H
H
No.
N
- Thn
(I sh-
P aeii aaa
p:sm (n) (Vitt1 R/
S 3
H
SHL N
No
n=1
N
I Leig - IP 2i aa A |b) ) *111
h+1 -Vitt) S / No
7a
NI
n=l
1=1
N
Q'i +
H
Th
Le h44
PP Nedion (al b. /b
Vhit1 S
N
N
1=
Here, the first conclusion because 0 S V (s) (9) S H and Σ 1/ S by (b)
of Lemma F.3. The second conclusion is proved by combining Equation (84) and Equation (90) and using V t..im aahii "A 1) S Q'. The third and fourth conclusions follow directly from E
d in Lemma G.1 and Equation (104), respectively. The last one is proved in Equation (106) with k.j.m bidio (VT+1) S Q Applying these five conclusions to Equation (127), we then reach:
N
@ - (5) k.j.m k.j.m a
S
(Vh+11 - -Vit (5 k" J" .m"
I [ 2 do]
n=1
QQ* + (,22)²
H
T [ 2 M] + 2 Z/....m
N
(N
and thus
Σ Rijim
p. (Q
(s . m)
wh
No
J. Wh
No.
(Var"
6r jm XI [ 2 iol
Pmn.
(5/+1
R.j.m
n=1
(Q+ + B²
H
+
j.m h
I[NA 2 MJ + Σ
wh Z zoosum
(128)
No.
(NT))
A.j.m
k.j.m
Similar to Equation (57), we can prove:
Σ k.j.m
k.j.m
(V Vit+z 3" .m" ) [N 2 i0]
Wh
Tn
n=1
S' m'' (vitz - Viita) (5/--1 d'd )
(129)
where
Σ I [N
2 10
wh
N
I [(k] ((,,,""m")) (K.55', mm))]
k.j.m
1=1
By Equation (30) in Lemma F.6, it holds that:
(V0= (Q- + 32H
H
Σ
k.j.m
[[ > M
w
N
(NT)
k.j.m
x V(0* 3.22 (22H)SAA
+ HSS (1W]),,,))
(130)
69

---

Applying Equation (129) and Equation (130) to Equation (128), we reach:
Σ J.j.
wh
(Q (1)(s km
,h k.)
R.j.m
Σ Wsh J. ma (V - Vittt) (s 5'
11 + + (
+ [S (IWWl))))))
Σ
W/
k.j. zk.j.m
2h
with I| & 1 and | S exp(3/ (wollsoh, Here, the last inequality because
Vil (6/+41 "' (8 .441
j'm an J' .m'" and V (s K .mm 2 Qh+ (5) 1441 h+1
( J' .m
.041
Now have developed recursive relationship for the weighted sum of Q Q7 between step and step h + 1. By recursions with regard to h, h + 1,... H, we finish the proof.
Lemma K.2. Under the event O & in Lemma G.I, for all e E (0, H), we have the following conclusion:
Σ I 1h
k.j. aa
Q7(5%
k.j. k.j.m >
,0
Amm R.J.m
(Q" B²H) H)
Be H
HTSA?
M
and
H
(hh Q%)
k.jm a. [00 Q7) (5
k.jm k.j.m .0h
o0h
1=1 k.j.m
Q + B HASAL
S²
B + SA².
Proof. Let N = [loga (H/c)]. For any i << N, k E [K] and given h E [H] let:
whi k.j.
1 k.j.m ,an k. (
( k.j.m
ohh k.j.)) [2-=1c e, 2'e2)
and
kjm WA,
(sh
k.mm an k.s. Qi (s) dp
k.s. [2N-1e, 11]
Then
max w k.j.
1 [|ll(()
Σ
k.j.
whi
k.j.an
k.j.m
Now for any i E [N], we have the following relationship:
J.jan (Q+: - -ii)
(s k.j.
aa 2 2e
(131)
R.J.m
Combining the results of Lemma K.1 and Equation (131), have:
2 eelwwl i.
2/ S H (Q+ + ( 1k (1
([W)))))
H
k.j. (h) (1)) dmm. WH'
W.jkm.j.m
< H (Q (2) (SA))
([W))())
Σ Σ
A. A.. (h) (132)
whi
M=hkd.m
70

---

where for any h S/ N/' - H -1
Whi
A...' (h) Wh,
k.j.
No io
w/ wh44,, (h) = E
mm W (h)I
N
2
1
m²) - (k, i, m)] [(k,
The definition of these coefficients is the same as that in Lemma H.4. By Equation (132), at least one of the following three inequalities holds:
2 e ellllll & H 1 (Q B
2 tellllll x (S)) (1| 11)))
2 2' Σ
Σ
k.j.m Whis
(h) 2 Z.
h'=h J.j.
Solving these three inequalities, we know that:
(Q* + 3²H H H.SA (2
Em=n h Enji
Whis (h) (h)2k:55m) j.m
R.j.
|
10 S max
4i-22
2--1c
Q' H) SA.
SA (2i-1c)
EH Ek.j.m Whi
J.J.m (h) 7.1,
(133)
2i-22
26-1e
We claim that
H Σ
Zkjj SA?
SM2
(134)
which will be proved later. Therefore, by
1[(h -ih) (... an
k.s. E
Σ
kjm
What
we have
H
H
N
T [
k..m a a...mmm
R.j.
(135)
A=1 k.d.m
h=1
1=1
By Equation (133), it holds that
N
+
H SA
N
SASAL
N
Σ Ei Ensm Wh:s M. (h) (1)
w
11h
4--222
(21-1e)
2
SAS
+
H)
SA
HASA
EN==
Ex...m Zk..m
22
2 SH*SA
1=1
(Q* H) H²
SA
SA
2
Be
O+*
+ 8 H
SA
S
S
24
(136)
2
Be
Here, (i) is because 0 & WHi K.S. (h) < 27 by Equation (67) and Zk...m 2 0. (ii) is because of
Equation (134). The last inequality because
S
BA
SAA
SA
SH
H
+
2
Be
Be
62
Be
71

---

by AM-GM inequality. Combing the results of Equation (135) and Equation (136), we finish the proof of the first conclusion. Further, we can prove the second conclusion by noting that
H
11
N
On @ - Q%) (6 k.i. II
[ - Q7) (8%
m.mm ked.
: .
2'
Vellolli.n
1=1 jm
1=
H) H2SA
H N
H
H
ΣΣΣ
+ΣΣ
Σ
Σ
(l))
Z
2
(2)
Whi
A=l
A= R Reg.o
(0'+3'1) SAA
HASA
27
ΣΣ>
E
e
Nej.an
Q + H) SAt.
STSA2
*MH
Here, (i) by Equation (133) and (ii) by Equation (67). The last inequality because of Equation (134) and
H+ BH'SA H'SA
H+SA
BH SA
B
B
by AM-GM inequality. Next, we only need to prove Equation (134).
Proof of Equation (134):
By definition of Z Z... (see Equation (125) in Lemma K.1), we have the following relationship
H2L+ + V H Rt.
NoW 170
H
HI HHI N io]
No
B2
H,
[ < N < M
NE.
(N
11
Nk Thn
W
+I
(V#41
h411 (s/411
I'm
P P anym M (DR.A -2RA4)) (137)
For the first term Equation (137), by Equation (73), we have
ΣV
No No H MHSSA.
(138)
h==1 k.j.m
For the second term of Equation (137), by Lemma F.6 with 1, we know
H
H2,
Σ
Σ
S &MH + S
(139)
NE. (8 a k.m)
W=
R.J.m.NK oo
By Equation (93), since 3 < H. holds that:
Σ
H
Σ
HT H k.m k.jmm
(WW aa K.j.my
S
+ MH
(140)
NE (s
B
#=1
k.j.m.,Nk 20
Combining the results of Equation (139) and Equation (140), we can bound the second term:
# Σ
H H ( (... k.j.m
)
H
*H SAC.
(141)
Nà (s
kjim
.01 k...
B
k
N...m.A... 50
72

---

For the third term of Equation (137), by Equation (122), we know
"
Σ
HI
<< N (s
m < i0 & MHASA
(142)
1==1 k.j.a
For the fourth term of Equation (137), by Equation (24) in Lemma F.6 with wf = and = 2.
we have
H
(V
(Q + 33H
H
1 < N (6 .aa. < M
No (s (s....m
.ak J...
N (
h 1 R.J.m
E
VH&I 0 (s
kam.
oa a M
SMHSAA
(143)
Here the first inequality is because Q S H and 0 S 3 S H.
For the last term of Equation (137), by the triangle inequality, we can bound it with
H
N
N
Σ
(V W+1
(
Tn
N
W= k.j.m. >0
n=
==1
Σ
Σ
Σ
DRR4'
V&K++1
mn
+1 h
== K.j,n, >0
#1
Σ
bR,K+1 N441
R.
k.m. k.m. a
W441
h'=1 K.j.m.N &
n=1
H$SA2 M S
(144)
B
The last inequality is by Equation (119) and Equation (124). Combining the results of Equation (138), Equation (141), Equation (142), Equation (143) and Equation (144), we completed the proof of Equation (134).
L Proof of Gap-Dependent Svitching/Commmicatioo Cost (Theorem 4.7 and Theorem 4.9)
L.1 Auxiliary Lemmas
Lemma L.1. We have the following conclusions:
(a) Under the event N Es, the following event holds for some sufficiently large constant co > 1:
E15
Σ
I [ - (s
k.m.j k.m.J)
aap
A min
1= R.j.m
(Q++B11) SAL ST
M M
Cmin
co
vh E [H]
A2 min
Amin
(b) For any deterministic optimal policy n², with probability at least
8, the following event holds:
E16 =
P.
an
k.j.m
+ n (8
k...m x
k=
j.m
R''
<3
k.j.m a
# m, ( + 21, vh E [H) e [k7}
k=1 J.m
73

---

(c) For any k' [ let Rg = =E j.m 1. which is the total number of episodes in the first kf
rounds. Then with probability at least 6, the following event holds:
817-
5h
k.jm
1=1 J.m
W
24
P
8/
R.j.m
= 5) s/17t)
c 91, As E E [[K]
1=1
J.m
(d) With probability at least - 8, the following event holds:
J22
E18
J.n. =s
P (S s 1
Ju k.j.m = s|(rh at +Illl 11,, V(s, k)
S
32
Here, under the full synchronization assumption, agent will generate Js episodes. Note that given the round k and the policy n², under random initialization assumption, the probability P(s) k.j. = =|x*) is independent of the index m, Let
assume that in the k-th round, each
p& s,h PP
k.a.m = s/ then E18 can be written as
Jk
Ess-
k.j.
JaPk sch
32JnP + 11l, k,
A
Proof. (a) is proved by Lemma K.2.
(b) We order all the episodes in the sequence following the rule: first by round index, second by episode index, and third by agent index. Let n(k: j. m) denote the position of the j-th episode of the m-th agent in the k-th round of the sequence. The filtration Fa(k.j.m) is the a r-field generated by all the random variables until the first n(k, J. m) episodes. When there no ambiguity, we will abbreviate ri(k, j, m) as n and Fn(....m) F... Then we have:
P
k.j. (
* the (5%
R.J.m
TP
di (y.. + (kk... Fr)
According to Theorem E.3, with probability at least - 5//T,, the following inequality holds for any given h 1 E [H],
Kg k' kg [2)] and Ryg
- k=1
Ej.
1 [Ti]:
k.j.m dn
# mHe (3 R.j.m
T
k.jaa ap
+ (
21, Vk' E [K].
1=1 J.m
3.m
Considering all the possible values of h = h'' E [H, = Ko E
[ and RN, = -kke
Σ j.m 1 E and Rs
[Ti), with probability least 8, holds simultaneously for all [H) K' E H
I
Ek Ej, [Zi] that
k'
IP (a
(alilim + ( (.i.m) nTt)
3
[
Jalao + (ohdh)))) + 2t.
Jam (c) According Theorem E.2, with probability at least 1 5/ST3. ? the following inequality holds
j.m
for any given s' E S. = h' E [H] k'' K/ E [7)1 and RAg Eke pm 1 [Ti]:
J.j.m Spr
s'}
k.j.m s' s'( =s( S V SN
24 Σ
P
k.j.m sy
s' 8/(7th) 9c.
1.m
j.m
74

---

Here, we let o² = TT, m [log2 (Ti)) in Theorem E.2 and
N/ W
A/
s.j.a =s'( sT( (1-P) j.j.
- = =s((TT))
- h
v.j..m = 5/(
1eml
2,m
3.
Considering all the possible values of s = s' E h' e [H] k' = kn 11 E [Til
with probability least 1 - 8, it holds simultaneously for all E S, h E [H] k [ and T E [Zi]
kv'
ΣΣ
k.j. = s) - P (5h (.....m (s) 3| =||= } - sh
24
Σ
k.j.m 8h
= s (
1t 9t.
k= J.m
k= f.m
(d) The proof is similar to (c), considering all the combinations of (s, (s,h,m, m, k, Rb) ESX x [M] x 4 x [Ti].
Lemma L.2. Under the event
for any given deterministic optimal policy x', we have
H
j.j.m
& Ai (.) I Cmin:
h=
R.J.m
Σ
P
0h
k.am
+ THt (57
x² S 4Cmin-
Here Cmin is the upper bound in the right-hand side of E1s in Lemma L.I.
Proof. For any h E [H), let the set Dr, be all triples of (s, a, h) such that a & As) that Dr. {(s, a, hala & AT(s)) We also let the set D = U Dú, and the set Dopt = {(s, a, h) E (s)}. Then we have [D] Dopel = SAH.
If for given (h, k, j. m.), (sh. ,a k.m.J h)) Dr. we have An ah m. Lemma H.1, we have
Amin- By
(5 j.j. an
max m (s k..m .a) 2 max max (T k.j. ,a)] = V% (5 mm k.).t))
Therefore, holds that
( .ah k.m. - 1% (6h k.m. oh N.m...) 2 (n ( " ahimm. 2 Amin-
Then we have
I %
k.j.
$ Aī (stammm))
(sh (s
ah
k.m. h) Dn.
I Qh
(sh
k.m.j
,ap _a a.m.j Q (..m. ,u4 s.moy 2 Amin]
and thus by the event E15 in Lemma L. it holds that
"
$ (s
dn
1= k.j.m
H
Σ
1
[o
tm aa (o k.m.d ah m.mdddd >
Amin
Cmin-
(145)
Au R.j.m
Next, we prove the second conclusion. Let Sh - {s Pii. 0}. For any given deterministic optimal policy n². we have
k.j.m I
# (1 (h.im))
kjm * ( buim ).
kim & so]
an
=
dh
sn
+
Oh
k.j.m f न (o 8/
kjm E 5R]]
(146)
75

---

For k.jm $ SSh. we have FT, 2 > and (6 h
= 1 by condition (b) of Definition 4.6.
This means mi (s k.. is the only element in AA (5/ m. Therefore, we have & 5%
k. # mे (s Sh
(...), k.mm
I [
k.j. (s (m)))))
(147)
For the second term in Equation (146), if = 1, because of the randomness of the selection of $1 A.j. we have P(81 = mu..
(m*) P(s1 $1 j. > 0 and then
k.j. a
mi (.s...mm $ k.j.m E S O.
(148)
To bound the second term in Equation (146) for 1, we first prove lemma.
Lemma L.3. For any h E [H] and the trajectory (. .a kjjm agent mn in round k, IP
"..."" ) ,5h 3i=1 in j-tt -h episode of k.j. at step > and az k.jm is the unique optimal action for state Sh.
8h 3...mm
h, then we have IP
.4+1
Proof. For any given optimal policy n², it holds that
P kaim 141 #611
TP
8h-1 = 8
R.j.m h+1
(T"))))
2 P 8h41
S/41
k.j.m
| |8h- 8h
j.j
On
kJm
xx**
x IP
5h.
k.j.
0
k.j.m
π
8h+1
k.jam Sh+1
8h
j.j.
an = an
k.j.
p
k.s.
>
8
The equation (I) by Markov property and
((sh
5h on an
k.j.m
k.j.m m
TT) P(
[T') = P 8%
kmdm
kidi
L
For every initial state M. we know P 2...m > Therefore, if for > 1, IP+
"n R.J.. and
8h k.j.m Sg. by Lemma L.3, know there exists h such that dz k.m.J. is not an optimal action > 0. Therefore, for the second term in
k,m.j at step h', otherwise we have P for state 8/'
p.....m
%
Equation (146), we have
h-1 S
TI kj.. "h
* (5
R.j.m). J.j. Sh
E 5% <
k.j.
E
S
k.j.m
& AA (1 (5/..:m)) (149)
M==1
By combining the results of Equation (147), Equation (148) and Equation (149), we can bound the Equation (146) as follows:
[ k.j.m # níj (8 J.m))
&
(hr
ap
k.j.m
& Ah.(st..mm)
h'=1
h==1
Therefore, using Equation (145), we reach
H & AZ (5 (stis.m)) S Cmin-
a Σ I R.j.
+ (1 R.m.m
Σ
Σ
T
a
k.j.
k.g.
k.j.m 1'=1
Combined with the event E16 in Lemma L.1, conclude that for any h [H] and W E [K],
kijm
# (
x²))
4Cmin-
4h
1= J.m
76

---

Let i1 = HH + 1)4, 22 = 6500 Ciia/ and Č 1/ 1)), For any (s.h) [H] such that s, 0, we use ní (s) denote its unique optimal action. Before proceeding. we present
lemmas. Lemma L.4 shows agent-wise simultaneous sufficient increase of visits for the triple (s, a, h) that satisfies the trigger condition in round & when N a) > i1.
Lemma L.4. Under the event ni= for any (s, a, h, k) E SxAx [H] x [K] such that N (s, a) > and the triple (8, a, h) satisfies the trigger condition (3) in round k, it holds that
* (1 (1+
Proof. If the trigger condition is met by the triple (s, h) in round k. then we have =T((s, For such (8, a, h), by E1 Lemma I..1, it holds for any E S, h E [H], k E [K] and m [M] that
k.t. = T k.jm 8, ah
Rjmm =s
JJPP", ",h 32. an 111, Ja s.h
32J s, 11c
(150)
Since (s, a. h) satisfies the trigger condition in round k, there exists an agent mo such that k.mo (8,a) (8) Then we reach nh
(s.a) 1 ON 299.. MH(H +
Jup s.h 32J s. 11
The last inequality is because Ni (s, a) > 41. Solving the inequality (i). it holds that
J.P h 2 VON - 31 V81.
Then by Equation (150), for any other agent m,
2 VBi)
k.j. 8h
s, s,ah
k.j.m = a) 2 Ja s.h V P2 e. 11
(J.P 8.h
199
CN +1
(CCN -3 -4- -2v8(
-19 2
The last inequality is because CN > 299t. Therefore, we have
J
M(CN +1)
(=,
(s, a)
Σ
m.k T
(s, a) Σ Σ
J.j. 8/
k.j.
8, ahh
a
3
3H(H +
j=1
and thus
+n((s,a)
1+
3H +1) (s.
Lemma L.5 shows the state-wise simultaneous sufficient increase of visits for states with unique optimal action.
1i=1 E, if there exists (so, ag, ho) S Ax [H], such that it satisfies the trigger condition in round k and Nk. (so, ao) + in, then ag E AZ (so). Moreover, if such (so, on, ho) also satisfies that Ip= sg 0, then
Lemma L.5. Under the event n 18
NO+ Nk+1(6 (8', The (s)) (1
holds for any (s',N') S [H] such that P 0.
77

---

Proof. Because N (So. ao) > i + 12 > Cmins by Lemma L.2. we know E AA (su). Next, we prove the second conclusion. Using the law total probability, for any 0 < h S H E S, and any given deterministic optimal policy x², we have the following relationship
k.j.m IP
= =s|T" (T))
hht1
8 h+t1 IP
k.j.
R.j.m (i(' (10)))(((()))))())) 1... s', ,0,0% Hidm ss, a.J.
k.j. =T(('')) 7*))
J.jjan
k.j.m F o 2 (0/ ).mmm 1
h+tl
8, Uh
p
s, it
IP s/2
k.j. ss, an k. (h'('') | m²t) +
(
k.j. sh41
= s, a
k.m. * 10 mtt).
(151)
where
ppk.j.m 9,
TP
sh+1
k.j.
8) s/
J.j. 8', an
k.j.m
(5((5')) mz)
=P IP
5| 5/58
R.j.m s', an
kim T,. (5))
The last equality is because of the Markov property. We also have
k.j.m = s| =
j.j. = s|8) k.j.m 8s, nt"
P ( J...m
8/1
= 5s s/|xx)
h+1
Σ
j. s,d' ah
P
( (% (st.s.m = s' s/1x*)
(152)
where the last equation is because
P( s/sh k.j.m s', TT" IP
Jija
k.j. sh41
s|s; k.j. s', dn
kj.m = -7
jm
8,8'
Combining the results of Equation (151) and Equation (152), then it holds
P
k.j. h+1
= -s/
k.j.m = s/TT² #/+11
pk.j.m
[P 18h..mm k.j. = s On
k.j.m
= ক,o ()())))77)) - IP (5 k.j.m s'(TT*)
h
+ P
Sht1
k.j.
= s, on
k.j. # (5tt )
Σ pkojom
IP
k.j.
5 1 m/t) =s
Tp (.).3.m ( k.j.m = 5' =s((xt)
8h
Σ
p....mp hh
(.....m s', an k. + mh (s') at) + P st.
s, an k.j.m * th (s m
Therefore for any 0 < h < H - and E S, by the triangle inequality, it holds that
k.j.m = s n - P h+1
k.j.m s/
h+11
phojim |P
J. n - TP (sh. k.j.m 8/1 x11x²))
pho..mp hh
(s = s',, an k.j.m + (T')s)) mth) + P ( (sh:irm
k.j. * ( m
s,a a.
Summing the above inequality for all s E S, since Eg Pe.ee = 1. then we can derive that:
Σ p
k...m = ss x²t) P h1t1
J.j.m = ss(rt) s141
P
Joijam = s' (1a²)= Pp ((tt k.j. = s/1xx) 2IP (a k.i. # o (5 x²) )²).
8h
78

---

Since P( P(s =s x²²) - P(( k.j.m s| O. by recursion, for any h' E [H] we have
Σ P 5/'
k.j.m = =s| 1T)) - IP (s = =s/TT)
2
P
hh
# m (5 xtt)
h=1
TP
an
k.j.
# t, (st..mm)) m²t) r
h=1
Using Lemma L.2, then for any h E [H] and k' E [K]. it holds that:
K''
k.j. = m²)
k.j.m = s|(x*
8h
5h
1=1 J.m
11 K
k.jm
+ t (5 kim x²/) S 88HCmin-
2
Oh
1=
j.m
Note that based on the property (b) of Definition 4.6, we have P(s) s|xx* ) P then for any
8 E
[H] and k' E [K]. by the triangle inequality, we also have
W
To.
k.mm 88
m**)
k=
j.m
RR
+
k.J. $p
= mTh)
P f... -Ps = = s Rg.P.,,, 8HCminn (153)
k=
j.m
Applying Equation (153) to E17 in Lemma L.1, for any S, [H] and k' [K], we have
k.
-P(sh
(sh.d.m = s|/7))
24
Pp
sh
k.j.m
s// 9c
1=1
k=1
J.m
V 24 [RNIP + 8.H
+ 9t
S 5 Rw 23HCmin
(154)
Combining the results of Equation (153) and Equation (154), by triangle inequality, derive the following relationship for any 8 E S, [M]. and E [K]
W
kijm =s] 5h
Ry s.h
Ry R P + 31HCCin 5
(155)
1=
Then by triangle inequality, it holds for any S. he E [H] and k' e [K] that
K'
k.j. 8h
8, ah
k.j.m
E Ai(s))
RE.IP.,,
A=1 J.m
k
5/ j.m
RR IP* a.
+
sh
k.m.
s, a
k.j.
$ Ah)s)
k=
j.m
S <5. R. P 32.1 Cminn
(156)
Here, the last inequality is by Equation (155), together with the fact from Lemma L.2 that
ΣΣ k.j.m
kJ.m & Ai)
k.j.m
& (s (.5 < Cmin-
8, a,
a
1=1 j.m
1=1 j.m
79

---

For Pa. > O. the optimal action is unique. Then for any (s,a, h) such that (s) and P > 0,
we can simplify the results of Equation (156) as follows:
Ry P // Rx.
P sn 32HC S N mr'++(ss ((s,a) S Rg + 5 R 32H min-
(157)
By Equation (157), for any s' 8 and h [H] such that IP; , O. we have
P A - // R no 32HC
N (T) [s (s)()"))
d P P + 5 & 32H miin
For the second conclusion, we only need to prove that, for any (s', E S [H] such that P >
R&PP N - /v RuP si 32/1Cmin
1
(158)
R . + / RK-1P= Ae o 32HCmin
6H(H +
Next, we will prove the Equation (158). For the triple (so, ao ho), by Equation (157), we know that 1o + +5 Rk-1
6500H
NK (su, S Rk-1P no
R s0. L
32HCmin
Cst
Solving the inequality, we have
6500H&Cmas
25c 5
V RrP ho
v
Rs RR-IPPP 80,
322HCmin +
Cat
6468H3CCm.
H3Cmin Cst
H3C
79,
(159)
Cst
Cst
Therefore, for any s' E and h/ E [ such that Por a by Equation (159), we have
V RReP' S > > R 0
P VCa 79 H3Cmin
(160)
For X > 6241 min = 792 H note that
/V
Cmin 32HCmin
X
5v 32HHCmi
(161)
56H2
Here, the first inequality is because 5 < Cuis
for H 2 2. Therefore, based Equation (159)
H
and Equation (160), we can apply Equation (161) to RE-1PP so P&P s0. Re- 1P= and RaPP
RE-1TP s0.ha
RgP.o.Ao
/ Rv- P 3o 32HC
Rs P+ so. 32H 5
50.eo
(162)
56H2
56H2
and
RgP S0,0
/ RI. 1P 32HH
5 RRP:: + 32HCmin
(163)
56H²
56H²
Since No. (s0, > i and the trigger condition is satisfied by (s, h) in round k, by Lemma L.4:
N an)
2 14
N ho (so, ao)
3H( +1)
Together with Equation (157), it holds that
RR ho
+ / R2 P+
32HCmin
Nk+11 (so, ao)
so
1
2 1+
(164)
Ry Ip h0
Ipt /v/ Ra-
32HCmin
No hg
(Sg, an)
3H + 1)
80

---

Applying Equation (162) to Equation (164), we have
R& ho ///e RR Rr so.ho" 1 32H
(1 + 56H2
1+ 3H +1)
R&-1 Ip* 8o. /v RK- 1P "o,no" 32HC
56H²
1
R
Therefore, using Equation (163), we have
R&P 2 - // RiIpy Ne 3 RR-1P + 5, Rs 1 ve o + 32HC
56/7 RS.
561 RR
3H H (11+11)) +1) )
(1-
2
1
56
(165)
56H2
Let
2
6112 + 6H +2
11
6 4H"
466 + 6H + 56/12
and thus
+ 6H(H+1)
6H + 6H
1
2
(1+c)
56
+ 3
6H + 6/1 +2
l
56
Applying this inequality to Equation (165) completes the proof of Equation (158), thereby proving the second conclusion.
L.2 Details of Final Discussion
In this section, we will discuss the number of communication rounds in four different situations:
Situation 1: In round k, the trigger condition is satisfied by (s, a, h) when (s, a) S i1. We will refer this as Type-I trigger.
For each time the trigger condition is met for (s, a, h), the number of visits to (s, a, h) increases by at least 1/(2M H + +)) times by Equation (3). Therefore, the maximum number of Type-I triggers for each triple (8, a, h), denoted (2(s, a, /t), satisfies
1(..0,))-2
I+ 2M +1)
S Si.
Therefore, we have (s a, h) = OM log(t)) and thus the number of rounds with Type-I triggers is bounded by
( <MMP'S (11))
8,0.h
In round k the triple (s, a, h) satisfies the trigger condition when in < No (s,a) < i + iz. We will refer this as a Type-II trigger if a & A7,(s) or E (7(s) and IP, 0, and as Type-III trigger if E (s) and P > 0.
Situation 2:
By Lemma L.4, for each time the trigger condition is satisfied by (s, a, h), the number of visits to (8, a, h) increases by at least 1/3H(H + 1) times.
For (s, ft) satisfying the type-II trigger, by Lemma L.2 and Equation (156), we know that the maximum visit number to (s, a, h) is /2 Therefore, the maximum number Type--I triggers for each triple (s, (s), h), denoted tz (s, a, h), satisfies
32HC
1+ 3H(H +1)
11
81

---

Therefore, we have (s, a. h) Type-II triggers bounded by
- O(H log Cong322Cmm/bbi) and thus the number of rounds with
32H
Σ t2(s,a,h) 8,0.8
H SA
i1
Situation 3: By (b) of Definition 4.6, we know (s) for a Type-Ill trigger. Therefore, the maximum number of Type-Ill triggers for each triple (s, (s), h),
(t). denoted la(s, n (+), h), satisfies
(s),)
(1+
+ S i2.
3H(H +1)
21
Therefore, we have iT S ((HHlog(i))) Because we only have HS triples of (s, (s), such that 2, > the number of rounds with Type-III triggers no more than
Σ ta(s, (As) & O H 5log (iz))
20
Situation 4: The trigger condition is satisfied by (s, a, h) in round k when (s, > ig. We refer to this type of trigger as Type-IV trigger.
By Lemma L.4, in this case, for each time the trigger condition is satisfied by (s, h),, have a E (s). we will first prove P7, = 0 in this case.
Let S. (ss. a (s), P.,. = 0}. By Equation (156), we know for (s, as h) E Sp. N as. S 32/HCmnn <i + i2. However, when the trigger condition is satisfied by (s, a, h) in round k. we have (s, a) i i2, which is contradicts the fact that N wK+1(p *x, a) in ig. Therefore the triple (s, a, h) satisfies that PP;,, > 0. By Lemma L.5, for any E S and N E [H]
h
such that P > 0, holds that
N (s', (TT
1+ 6H(H +1)
(
Therefore, the maximum number of Type-IV triggers, denoted t, satisfies
[+ 6H(H +1)
T
T
i i HSA
Then the number of rounds with Type-III triggers is bounded by
log(
HSA)
T HSA
t4 log (H(H+T]
O
H2 log
Combining these four cases, the number of rounds is than
Σ h() + Σ (2(8,a,))
Σ
la(s, (s), 44
8,a
s.a.h
s.P >0
H2/HCin
HSA ))
T
00
MH (ti) + SA
+ S (iz) + +H² H2
i1 S AA min
(
(1)
T HSA
)).
<0 SHloS (MHi) SAAlo
+ S
122 log
Cse
When = 1 the number of communication rounds is upper bound for switching cost.
82

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and introduction clearly and accurately summarize the paper's contribution and scope.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Please refer to the details in Section 3.1, we discuss the different types of heterogeneity federated learning.
Justification:
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-speciiiatiinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g. if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
83

---

Answer: [Yes]
Justification:
Please refer to the details in our paper.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: We have discussed the syper-parameter choice to replicate the result and provided the code.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is new model (e-g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path reproducing verifying the results. 5. Open access to data and code
84

---

The authors should provide scripts to reproduce all experimental results for the new reproducible, they Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: The code that can exactly replicate the numerical results is uploaded in supplementary materials.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.. cc/
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: / cii.ps.cc/publii coubblicguiidee twtp////eeee/eee// CCodeSubmeaaac ssi asionnooicyy for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
proposed method and baselines. only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The choice of hyper-parameters has been provided in the numerical section.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: We report medians and two other quantiles based on multiple replications in the numerical section.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
85

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative rates).
show in tables or
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: We have included a description of related computational resources in the footnotes of numerical section.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that NeurlPS Code of Ethics https: http://neuippppeeeee cc cc/ppbliic/thiicccuieieeeee
didn't make into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the
Answer: [Yes]
Justification:
We review and follow the code of ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive socictal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This is theoretical work.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
86

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
Safeguards
Question: Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification:
This is a theoretical work and there no such risk.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification:
We have cited the source of the publicly available code we referred to.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperswithcode. thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
87

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moddl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Bthies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such the institution conducting the review.
88

---

16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: The core method development in this research does not involve LLMs as any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (https:/ /ttps/////euu...eeeeee www.arips.c/oooefeeeeeeeeeeeeeee /00/////eeene//222/////// 20LL/LLM for what should or should be described.
89


Reviews:
[{"review_id": "N67SIeaeZm", "reviewer": "Reviewer_CTk9", "summary": "This paper proposes a novel variant of the Q learning algorithm, and its federated counterpart, achieving both low switching cost and lower burn-in cost.\nThese algorithm, Q-EarlySettled-LowCost and FedQ-EarlySettled-LowCost, combine an upper confidence and a lower-confidence approach, together with the construction of a reference estimator, to reduce the burn-in cost.\nBoth methods are studied in terms of worst case dependence and gap-dependent bounds, achieving low switching cost in all cases.\nIn particular, the federated method achieves regret that grows in $\\sqrt{M}$, where $M$ is the number of agents.", "questions": "1. Is there hope to reduce the number of communications, so that it does not scale linearly with $M$ anymore? Could the ideas presented in [1] be applied to this setting?\n2. In the experiments presented in appendix, it seems that the proposed algorithm outperforms all other flavor of Q learning. How does this compare with model-based methods? Overall, I think it would make sense to include these experiments in the main text.\n3. The obtained burn-in cost remains quite large, although it depends only linearly on S, A. Is there hope for further improvements?\n\nLabbi, S., Tiapkin, D., Mancini, L., Mangold, P., & Moulines, E. (2024). Federated UCBVI: Communication-Efficient Federated Regret Minimization with Heterogeneous Agents. arXiv preprint arXiv:2410.22908.", "limitations": "The discussion on the cost of communication is missing, although it can quickly become a problem in large scale federated RL cases.\nSimilarly, the relevance of the homogeneity assumption should be discussed.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n1. The proposed Q-learning methods are the first methods to achieve both low switching cost and low burn-in period. Reducing the burn-in period is crucial to achieve meaningful guarantees in RL, while low switching cost is essential in federated RL, in order to keep clients synchronized on the same policy without requiring a prohibive number of communications. Providing a method that achieves both is a significant open problem.\n2. The federated algorithm indeed benefits from collaboration with other agents, with a summed regred scaling in $\\sqrt{M}$ (i.e., averaged regret scaling in $\\sqrt{1/M}$).\n3. The proposed construction is a clever combination of upper and lower confidene bounds, allowing for early settlement of the reference function, which in turn significantly reduces the burn-in period.\n\n**Weaknesses**\n1. The proposed method unfortunately requires important number of communications, and grows in $M \\log(T)$ for worst-case bounds and $M \\log(\\log(T))$ for gap-dependent bounds. This may quickly become prohibitive in large-scale federated RL scenarios.\n2. The FL scenario that is considered is the fully heterogeneous scenario, which is not the most common in federated learning. Although I think the paper already presents interesting results, it would be interesting to discuss possible extensions to the non-homogeneous case.\n\nThe following reference, which studies Fed-UCBVI is missing from the discussion of related work, and may provide insights for possible extensions reducing the dependence on M of the communication :\n\nLabbi, S., Tiapkin, D., Mancini, L., Mangold, P., & Moulines, E. (2024). Federated UCBVI: Communication-Efficient Federated Regret Minimization with Heterogeneous Agents. arXiv preprint arXiv:2410.22908.", "was_revised": true, "final_justification": "After the authors' response, I remain positive about this paper. I appreciate that the authors considered adding additional experiments with model-based methods.\n\nI remain skeptical about their notion of heterogeneity on the \"exploration speed\", which, to my knowledge, is not defined neither in the authors' manuscript nor in [1], nor in the existing literature. In particular, the reviewers claim that the number of communications has to increase with the number of agents $M$, which is not clear and contradicts other existing work. This is not detrimental to acceptance, but I would appreciate if the authors could discuss this in more detail in the revised manuscript.\n\nRegarding the non-homogeneous case, the authors claim that all existing results exhibit a regret that scales linearly in T when agents are not homogeneous, which is true. Nonetheless, these results prove that the method works in slightly heterogeneous settings, up to a small additional error: in the results presented in the current manuscript, no such analysis is proposed, and this is an important limitation in the paper, since heterogeneity is one of the key factors of federated learning.\n\nDespite these remarks, which I would appreciate if the authors can comment on", "rebuttal": "We thank you for your careful reading and thoughtful comments. Below are our point-by-point responses, and we hope our responses address your concerns.\n\n>### **Weakness 1 part 1 and Question 1: The linear dependency on $M$ in the number of communications**\n\nThank you for raising this important point. We also appreciate your mention of the reference [1, Labbi], which we will cite in the revised manuscript.\n\n[1] proposes a model-based online FRL algorithm, Fed-UCBVI, and analyzes its communication cost. For comparison: in worst-case setting, our work provides the bound $O(M\\log T)$, and both [1] and our gap-dependent analysis provide the bound $O(M\\log\\log T)$ under a homogeneous exploration speed assumption. Notably, we can refine our worst-case bound to match this improved communication rate under the same assumption. However, **no existing method eliminates the linear dependence on $M$ in general**, and the techniques in [1], which share similarities with our gap-dependent analysis, do not overcome this either. We elaborate below.\n\nThe linear $M-$dependence in our method arises from the event-triggered termination condition (Eq. 3), where the threshold $c_h^k$ is scaled by $1/M$ to ensure that the total number of visits to a state-action-step triple across all agents is controlled in each round. In our worst-case analysis, we do not assume that the agents explore the environment at the same speed, so that each agent can generate different numbers of episodes in a given round. As such, the uniform threshold $c_h^k$ ensures robustness to heterogeneous agent exploration speeds, but results in a communication bound of $O(M\\log T)$.\n\nIn contrast, under the **homogeneous exploration speed assumption** used in both [1] and our gap-dependent analysis, all agents generate the same number of episodes per round. Since they share a common policy, the visits are i.i.d., and the law of large numbers implies that once one agent meets the threshold for a triple, the others are likely close to meeting it as well. In Lemma L.4, we have shown that when the visit count exceeds $i_1=\\tilde{\\Theta}(M)$, this concentration effect enables a global synchronization that helps remove the $M-$dependency of the number of communication rounds in the late stage with high probability. This reduces the overall $M-$dependency to $O(M\\log\\log T)$, which is caused by the early stage and remains unavoidable even under this assumption.\n\nIn summary, although our method inherits a linear $M$-dependence in communication cost, this is a fundamental limitation shared by most existing FRL algorithms aiming for optimal regret guarantees. We can refine the bound in our worst-case analysis if we assume a homogeneous exploration speed as in [1] and our gap-dependent analysis. However, such an idea cannot remove the linear dependency on $M$ due to the early stage. We also remark that the bound $O(M\\log T)$ holds deterministically, but the bound $O(M\\log \\log T)$ holds with high probability, due to the concentration arguments.\n\n>### **Weakness 1 part 2: The large-scale FRL scenarios**\n\nWhile removing the linear $M$-dependence remains an open problem in general FRL, we note that, in large-scale FRL scenarios (i.e., when $M$ is large), it is possible to remove the $M-$dependency **by allowing waiting time**, similar to the strategy used in FedQ-Advantage [109].\n\nSpecifically, we can modify our algorithms so that each local agent terminates exploration in a round only when it independently triggers the synchronization condition, without relying on signals from other agents. In this situation, each agent, rather than just one in our current algorithm, ensures it collects a sufficient number of new visits in a round for at least one triple before proceeding. This modified design removes the need to coordinate exploration speeds across agents.\n\nWe formalize this in the following result that will be added to the revised manuscript:\n\n**A New Theorem.** For the modified FedQ-EarlySettled-LowCost (Algorithms 1 and 2 with $\\beta\\in(0,H]$ and the modified synchronization condition), define $\\tilde{C} = H^2(H+1)SA$. Then, the number of rounds $K$ is bounded by $4\\tilde{C}+ 8\\tilde{C} \\max\\\\{\\log(T/\\tilde{C}),1\\\\}.$\n\nThis new bound eliminates the linear dependence on $M$. This improvement comes at the cost of waiting time, as agents who complete exploration early must wait until slower agents also reach the synchronization condition. For more general scenarios, especially under heterogeneous agent behaviors, further research is required into new synchronization strategies and regret-communication trade-offs.\n\n>### **Weakness 2: The non-homogeneous case**\n\nWe appreciate the reviewer’s suggestions for possible extensions to the non-homogeneous case. The literature on online FRL discusses two key forms of heterogeneity: (a) Heterogeneous exploration speed, where agents generate different numbers of episodes per round, as discussed in [108, 109] and this paper, and (b) Heterogeneous reward functions and transition kernels across agents, as discussed in Fed-UCBVI. While our current paper addresses (a), we agree that (b) is an important and challenging direction, and we elaborate on it below.\n\nFed-UCBVI provides theoretical guarantees under heterogeneity (b) by leveraging centralized value functions and Bellman equations. In principle, a similar analysis could be extended to model-free FRL algorithms, including ours. However, the resulting regret bounds for both Fed-UCBVI and hypothetical model-free extensions inevitably lead to the **linear dependence on $T$**, highlighting a key limitation: none of these methods fully mitigates the bias introduced by heterogeneity (b).\n\nThe main technical challenge arises from **heterogeneous visiting probabilities** for any given $(s,a,h)$ across agents. Even when agents share the same policy, heterogeneous environments result in different numbers of visits across agents. This causes an imbalance in sample contributions across agents, making the **standard equal-weight aggregation** used for the Q-update in all existing online FRL algorithms inherently biased.\n\nTo overcome this issue, a promising direction may involve **weighted aggregation schemes** based on agent-specific visitation counts, as explored in some offline FRL papers [88, 89]. Adapting such techniques to the online setting could help address the bias introduced by heterogeneity, though doing so would require a careful redesign of both the algorithm and its theoretical analysis. We view this as an important direction for future work.\n\n\n>### **Question 2: Comparison with model-based method**\n\nThank you for your suggestion and we will include these experiments to the main text.\n\nTo address the comparison with model-based methods, we include an evaluation against Fed-UCBVI, the only known online model-based FRL algorithm with near-optimal regret guarantees. We conduct experiments on the same two environments described in Appendix B, with $(H,S,A) = (5,3,2)$ and $(7,10,5)$, using $M=10$ agents. For each method, we report both regret and communication round performance over 10 independent runs, using the same hyperparameter settings for Fed-UCBVI as specified in [1]. The results show that our algorithm achieves consistently lower regret than Fed-UCBVI, while Fed-UCBVI demonstrates lower communication rounds due to its use of transition kernel estimations. In terms of memory, Fed-UCBVI requires $\\Theta(S^2)$, while our method requires only $\\Theta(S)$, offering a substantial advantage in scalability. We summarize the regret results (rounded to the nearest integer) in two tables below.\n\n**Table 1: Median regret at different episode number for $(H,S,A)=(5,3,2)$.**\n\n|Algorithm|10000|50000|100000|150000|200000|250000|300000|\n|-|-|-|-|-|-|-|-|\n|Fed-UCBVI|917|965|971|975|977|978|978|\n|Ours|444|623|676|699|716|730|735|\n\n**Table 2: Median regret at different episode number for $(H,S,A)=(7,10,5)$.**\n\n|Algorithm|50000|100000|500000|1000000|1500000|2000000|\n|-|-|-|-|-|-|-|\n|Fed-UCBVI|18398|19092|23045|28767|32038|35477|\n|Ours|9405|11961|18777|21920|23749|25046|\n\n>### **Question 3: The burn-in cost**\n\nThank you for raising this important point. Theorem 4.3 with $\\beta=\\Theta(1)$ provides the worst-case regret guarantee of FedQ-EarlySettled-LowCost as $\\tilde{O}(\\sqrt{MH^2SAT}+H^6SA+MH^5SA)$, where the additional terms $\\tilde{O}(H^6SA + MH^5SA)$ lead to the burn-in cost of $\\tilde{O}(MSAH^{10})$. Next, we discuss below the nature of the dependencies on $M,S,A,H$.\n\nThe **linear dependence on $M$** is unavoidable in online FRL because each local agent must explore the environment using suboptimal policies. Such dependency also appears in [1, 108, 109].\n\nThe **linear dependence on $SA$** is also unavoidable in online RL because the agent must explore the entire environment using suboptimal policies. Our method enjoys a lower burn-in cost than FedQ-Advantage and Fed-UCBVI, both of which show super-linear dependence on $SA$. In fact, this linear dependence is supported by the information lower bound in [102], which shows that even single-agent RL incurs a burn-in cost of $\\Theta(H^2SA)$.\n\nThe **super-linear dependence on $H$** is better than that of FedQ-Advantage, while model-based methods such as Fed-UCBVI exhibit better dependence on $H$ by estimating the transition kernels, but at the cost of higher memory requirements $\\Theta(S^2)$ vs. our $\\Theta(S)$. Notably, there is room for improving our $H$-dependence by possibly enhancing the Hoeffding-type Q-update (Eq.9 and 13) using more advanced techniques, such as Q-learning with momentum ([2]), which may accelerate reference settling and improve convergence. We view it as a promising direction for future work.\n\n[2] Pierre Ménard, Omar Darwiche Domingues, Xuedong Shang, and Michal Valko. \"Ucb momentum q-learning: Correcting the bias without forgetting.\" ICLR 2021.\n\n(All reference numbers in this response, except for [1] and [2], are from our paper.)"}, {"review_id": "dcuPDBvCo9", "reviewer": "Reviewer_a3AW", "summary": "This paper proposes two novel model-free reinforcement learning algorithms, Q-EarlySettled-LowCost for single-agent RL and FedQ-EarlySettled-LowCost for federated RL (FRL). The algorithms achieve near-optimal regret bounds while simultaneously ensuring low burn-in costs (i.e., the number of samples required to reach near-optimality) and logarithmic policy switching or communication costs. The design combines upper confidence bound (UCB) techniques with a reference-advantage decomposition and incorporates lower confidence bound techniques with an early-settling mechanism for reference functions in estimation. Meanwhile, the so-called ``Event-Triggered Termination of Exploration'' technique is also used in the proposed algorithm. Theoretical guarantees are provided in both worst-case and gap-dependent settings. Numerical results demonstrate superior regret performance compared to existing model-free baselines.", "questions": "The author(s) may wish to more clearly explain the technical challenges and their technical contribution --- especially which analysis, besides Lemma I.3, is new.", "limitations": "Yes.", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths\n\n+ The paper proposes the first algorithm that simultaneously achieve near-optimal regret, linear burn-in cost in $S$ and $A$, and logarithmic switching/communication cost under both single agent RL or FRL setting.\n    \n+ The authors provide improved gap-dependent regret bounds and establish the first gap-dependent switching cost guarantee for LCB-based algorithms.\n\n+ Theoretical results are supported by experiments that verify the improved gap-dependent performance in practice.\n\n+ The algorithm is well-engineered: by carefully tuning the bonus terms, it smoothly integrates existing methods such as Q-Early Settled-Advantage and Event-Triggered Termination of Exploration.\n\n\n\nWeaknesses\n\n- The technical contribution seems incremental. The algorithm essentially combines multiple components from prior work under the same setting. Key techniques such as Reference-Advantage Decomposition, LCB-based Early Settlement, and Event-Triggered Termination have all appeared in previous studies. Furthermore, the main analytical challenge, namely the non-adaptiveness of weights and reference functions, is addressed through direct application of surrogate function constructions from earlier studies, rather than by introducing novel analytical tools. While the author(s) have clearly invested substantial effort in assembling these components into a comprehensive (over eighty-page) manuscript, it is debatable whether such a narrowly scoped variation of the tabular RL problem warrants this level of complexity, particularly given the method’s modest empirical performance, as discussed below.\n\n- Empirical performance seems not very practically useful: under $(H, S, A) = (7, 10, 5)$, the regret and switching cost grow with $\\ln T$ at a scale of roughly 1000, indicating the constants hidden in the theory are large and the algorithm may not be practical for moderate horizons.", "was_revised": true, "final_justification": "I thank the author(s) for their considerable efforts in preparing the paper and for addressing the questions during the rebuttal period. However, I find that both the problem studied and the proofs are essentially direct combinations of existing works. Furthermore, several parts of the analysis appear incremental rather than representing a substantial technical contribution. Therefore, I maintain my score.", "rebuttal": "We appreciate your careful reading and thoughtful comments. Below are our point-by-point responses, and we hope our responses address your concerns.\n\n>### **Weakness 1 and Question: Technical contributions**\n\nWe respectfully disagree with the view that our method simply combines prior techniques. Instead, we have developed novel analytical tools that go beyond prior work. Appendix C provides a detailed discussion of the challenges and our corresponding contributions. Below, we further clarify why our contributions go beyond incremental advances.\n\n**Challenge 1: Non-adaptiveness of weights and reference functions**\n\nPrevious works only addressed isolated aspects of non-adaptiveness: [1] applies round-wise approximation for non-adaptive weights, and [2] uses the empirical process for settled reference functions. However, **no prior work simultaneously resolves both forms of non-adaptiveness**, and their direct combination introduces substantial technical difficulties. Notably, the empirical process in [2] incurs an extra $\\log T$ factor due to $\\epsilon$-net construction over non-adaptive reference function classes. When combined with round-wise approximations, the existence of nonadaptive weights can increase the effective dimension of the $\\epsilon$-nets, leading to looser regret bounds. It would require a new proof idea to solve this non-trivial challenge.\n\n**Contribution 1: Unified treatment via surrogate reference functions**\n\nWe address both forms of non-adaptiveness by integrating the **surrogate reference function** technique from [3], originally developed for gap-dependent analysis, into our **worst-case regret framework**. This enables a new decomposition that improves both theoretical bounds and generality. Specifically, our framework can be applied to existing reference-advantage-based RL methods [2, 4, 5], tightening their regret bounds. In model-free RL or FRL, worst-case regret is typically bounded by relating regret to the estimation error of the optimal $Q$-function, that is $\\sum_{k,j,m}(Q_h^k-Q_h^\\star)(s_h^{k,j,m},a_h^{k,j,m}).$ Prior methods upper-bound each term via $Q_h^{\\text{R}}-Q_h^\\star$ and then bound the sum recursively over $h$. Specifically, based on the reference-advantage update rules (Eq. 11, 15), with high probability, $Q_h^{\\text{R},k}-Q_h^\\star\\leq\\mathcal{G}_0$, where $\\mathcal{G}_0$ is defined in Appendix C.\n\nFollowing the structure of the reference-advantage decomposition, and using the **surrogate reference function** $\\hat{V}\\_h^{\\text{R},k}$, $\\mathcal{G}\\_0$ can be upper bounded by the summations with respect to $C_B,\\hat{\\mathcal{G}}\\_1,\\hat{\\mathcal{G}}\\_2,\\hat{\\mathcal{G}}\\_3,\\hat{\\mathcal{G}}\\_4$, where $C_B$ collects some constants and the cumulative bonuses, $\\hat{\\mathcal{G}}\\_1$ reflects the estimation error $V_{h+1}^{k}-V_{h+1}^\\star$, $\\hat{\\mathcal{G}}\\_3$ reflects the reference settling error $V_{h+1}^{\\text{R},k}-\\hat{V}\\_{h+1}^{\\text{R},k}$, and $\\hat{\\mathcal{G}}\\_2,\\hat{\\mathcal{G}}\\_4$ reflect the empirical estimation error for the settled advantage function $V_{h+1}^\\star-\\hat{V}\\_{h+1}^{\\text{R},k}$ and surrogate reference function $\\hat{V}\\_{h+1}^{\\text{R},k}$.\n\nIn contrast to the original decomposition from [2], where non-adaptive weights and non-adaptive reference functions together result in looser regret bounds, our surrogate reference function is **adaptive**, mitigating both issues. The adaptive design ensures that non-adaptive weights, which reflect delayed policy switching, is incorporated without introducing additional error via empirical process tools. As a result, we achieve a $\\log(SAT/p)$ improvement in the regret bound over Q-EarlySettled-Advantage [2], marking the **first application of surrogate reference functions in worst-case RL** and significantly expanding the analytical tools for RL that overcome limitations in [2, 4, 5].\n\n**Challenge 2: Balancing low switching cost and regret**\n\nIn online RL, achieving a logarithmic policy switching cost typically relies on delayed policy updates, as in [6, 7]. However, delayed policy updates introduce extra regret, since the same policy is reused across episodes before any state-action-step triple reaches a predefined threshold. This trade-off explains why, the low-switching-cost variants of UCB-Hoeffding and UCB-Bernstein ([6]) underperform their standard counterparts, as shown in Figure 1. How to achieve better regret at a low switching cost with delayed policy updates remains a significant challenge.\n\n**Contribution 2: Two-sided confidence bounds for improved bonus design**\n\nWe introduce a **new two-sided variance bound** to tighten regret under delayed updates in the proof of the optimism property ($Q_h^k\\geq Q_h^\\star$, Lemma H.1). Specifically, we derive both upper and lower bounds on the variance estimator (Eq. 33, 37, 38), whereas prior works such as [2] only use the lower bound. This refinement leads to more accurate confidence intervals in parts (b) and (c) of Lemma G.1 and allows us to improve the bonus term $\\beta_h^R$ in the reference-advantage decomposition, reducing the cumulative bonus $C_B$ and yielding both tighter regret and better empirical performance.\n\nAdditionally, to integrate this with a round-based design, we adapt the variance estimator by using one estimator in early rounds and another in later rounds, as detailed in Eq. 8 and 12. This adaptive approach ensures consistent accuracy of the bonus term across different phases of learning.\n\n**Challenge 3: LCB with round-nased design**\n\nFedQ-Advantage [5] settles reference functions only after a state-step pair has been visited sufficiently often, which introduces a polynomial dependence on $S,A$ in the bound for $V_h^{\\text{R},K}-V_h^K$, resulting in high burn-in cost. This dependence limits the practicality in large-scale environments.\n\n**Contribution 3: LCB-triggered reference settling for reduced burn-in cost**\n\nWe are the first in the literature to apply the LCB technique in FRL. In our design, $V_h^{k}$ and LCB-estimates $V_h^{\\text{L},k}$ serves as upper and lower bounds for $V_h^\\star$. The reference function is settled once $V_h^k-V_h^{\\text{L},k}\\leq\\beta$, ensuring $V_h^\\star\\in[V_h^{\\text{L},k},V_h^k]$. This allows us to settle the reference earlier and bound the settling error $\\hat{\\mathcal{G}}_4$ more tightly, reducing dependence on $H,S,A$.\n\nTo accommodate the round-based design of FRL, we modify the standard LCB strategy used in single-agent RL: early rounds adopt the same design as in the single-agent setting, while late rounds use an equal-weight estimator (Eq. 14), balancing accuracy with communication efficiency.\n\n>### **Weakness 2: Empirical performance**\n\nNotably, the $HSA$ term in the coefficient for both regret and switching/communication cost is **unavoidable**. In fact, [8] provides a lower bound of $\\tilde{\\Omega}(HSA/\\Delta_{\\min})$ for single-agent RL, demonstrating that any algorithm must incur regret with a coefficient that scales linearly with $HSA$. Similarly, [7] proves a lower bound $\\tilde{\\Omega}(HSA)$ on switching cost for any algorithm with $\\tilde{O}(\\sqrt{T})$ regret, highlighting that the coefficient of switching/communication costs must also grow linearly with $HSA$.\n\nImportantly, model-free RL algorithms with larger theoretical regret constants and $O(T)$ switching/communication cost are already used in practice. For example, in single-agent RL, [9] proposes Action-Robust Q-learning based on UCB-Hoeffding, which has a regret bound of $\\tilde{O}(\\sqrt{H^4SAT})$, corresponding to a coefficient larger than 10,000 in our setting (see Figure 1, UCB-Hoeffding), and incurs a switching cost scales as $O(T)$. Nevertheless, the algorithm performs well in Cliff Walking, a text-based environment with $(H,S,A)=(100,48,4)$, and Inverted Pendulum, a control task simulated in MuJoCo with $H=100$. Similarly, [10] extends UCB-Hoeffding to a multi-agent setting for cooperative navigation with $10^4$ states. Despite a regret bound of $O(H^6SA\\log(T)/\\Delta_{\\min})$ with a coefficient over 10,000 (see Figure 3, FedQ-Hoeffding) and a communication cost scales as $O(MHSAT)$ under full communication, the algorithm still achieves strong empirical results.\n\nTherefore, large constants (especially those polynomial in $H,S,A$) do not preclude practical effectiveness. In comparison, our algorithm achieves smaller coefficient than other baselines (Figures 1–4), demonstrating practical utility even in moderate-horizon settings.\n\n[1] Zhong Zheng, Fengyu Gao, Lingzhou Xue and Jing Yang. Federated Q-learning: Linear regret speedup with low communication cost. ICLR 2024.\n\n[2] Gen Li, Laixi Shi, Yuxin Chen and Yuejie Chi. Breaking the sample complexity barrier to regret-optimal model-free reinforcement learning. Information and Inference, 2023.\n\n[3] Zhong Zheng, Haochen Zhang and Lingzhou Xue. Gap-dependent bounds for Q-learning using reference-advantage decomposition. ICLR 2025.\n\n[4] Zihan Zhang, Yuan Zhou and Xiangyang Ji. Almost optimal model-free reinforcement learning via reference-advantage decomposition. NeurIPS 2020.\n\n[5] Zhong Zheng, Haochen Zhang and Lingzhou Xue. Federated Q-learning with reference advantage decomposition: Almost optimal regret and logarithmic communication cost. ICLR 2025.\n\n[6] Yu Bai, Tengyang Xie, Nan Jiang and Yu-Xiang Wang. Provably efficient Q-learning with low switching cost. NeurIPS 2019.\n\n[7] Dan Qiao, Ming Yin, Ming Min and Yu-Xiang Wang. Sample-efficient reinforcement learning with loglog(t) switching cost. ICML 2022.\n\n[8] Haike Xu, Tengyu Ma and Simon Du. Fine-grained gap-dependent bounds for tabular mdps via adaptive multi-step bootstrap. ICML 2021.\n\n[9] Guanlin Liu, Zhihan Zhou, Han Liu and Lifeng Lai. Efficient Action Robust Reinforcement Learning with Probabilistic Policy Execution Uncertainty. TMLR 2024.\n\n[10] Justin Lidard, Udari Madhushani and Naomi Leonard. Provably efficient multi-agent reinforcement learning with fully decentralized communication. ACC 2022."}, {"review_id": "MU8mDT6UsS", "reviewer": "Reviewer_Rdno", "summary": "This paper aims to simultaneously reduce the **burn-in costs** and **policy switching costs** (for the single-agent RL setting)/**communication costs** (for the federated RL setting). The proposed algorithm improves over [1] by a logarithmic factor in the regret bound and a polynomial factor in the burn-in costs.\n\n[1] Zheng, Z., Zhang, H., & Xue, L. (2025). Federated Q-learning with reference-advantage decomposition: almost optimal regret and logarithmic communication cost.", "questions": "1. I think the notation $\\Omega(\\cdot)$, instead of $O(\\cdot)$, should be used in the lower bounds in Lines 24 and 50. \n2. In the numerical experiments, how do the proposed algorithms compare to FedQ-Advantage regarding communication costs?\n3. Can you explain how FedQ-EarlySettled-Advantage reduces the burn-in costs in the FedQ-Advantage algorithm [1]?\n4. I think visualizing the burn-in costs in Figures 1 and 3 also helps highlight the improvements over the previous algorithms, for example, comparing the number of iterations where those curves \"settle down\".", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 1, "significance": 2, "originality": 2, "strengths_and_weaknesses": "* **Strengths:**\n    1. The improvements in the burn-in costs are considerable (i.e., polynomial to $S,A,$ and $H$), which could be helpful in the applications;\n    2. This paper presents a comprehensive regret analysis of the proposed algorithms and derives both the high probability and gap-dependent regret bounds.\n\n* **Weaknesses:**\n    1. The presentation is a bit unclear. For example, I think it would be better to put the exact bounds in Tables 1 and 2 to make comparisons between different algorithms. On the other hand, in the Numerical Experiments Section in Appendix B, the algorithm does not compare to [1] in terms of switching/communication costs;\n    2. The techniques utilized in this paper, including the reference-advantage decomposition and the combination of UCB and LCB methods, have been discussed in several references [1, 2], and their combinations and applications to a federated setup seem to be rather direct.\n\n[1] Zheng, Z., Zhang, H., & Xue, L. (2025). Federated Q-learning with reference-advantage decomposition: almost optimal regret and logarithmic communication cost.\n\n[2] Li, G., Shi, L., Chen, Y., Gu, Y., & Chi, Y. (2021). Breaking the sample complexity barrier to regret-optimal model-free reinforcement learning.", "was_revised": true, "final_justification": "After reading the authors' response, I appreciate their efforts to address my problems. I maintain my recommendation for acceptance as this paper provides a comprehensive analysis of federated RL. On the other hand, I think adding the table and the numerical results on the burn-in cost can improve the readability.", "rebuttal": "We thank you for your careful reading and thoughtful comments. Below are our point-by-point responses, and we hope our responses address your concerns.\n\n>### **Weakness 1 part 1: Exact bounds in Tables**\n\nWe follow this helpful suggestion and provide updated tables with explicit bounds to facilitate clearer comparisons. \n\nWe first define the following notations: $\\iota=\\log(SAT /p)$, where $p\\in (0,1)$ is the failure probability; $C_g=SA\\log(T)/\\Delta_{\\min}$; $\\mathbb{Q}^\\star:=\\max_{s,a,h}\\{\\mathbb{V}\\_{s,a,h}(V_{h+1}^\\star)\\}\\in[0,H^2]$; $\\beta\\in (0,H]$ is an arbitrarily predefined hyper-parameter; and $O^\\star$ only captures the main $\\log T$ term. The following tables show that our algorithm achieves state-of-the-art performance in both regret and switching/communication costs (Our detailed switching/communication cost results can be found in Theorems 4.6 and 4.8).\n\n**Table 1: Comparison of model-free online single-agent RL algorithms.**\n|Algorithm|Worst-case regret|Burn-in cost|Gap-dependent regret|Switching cost|\n|-|-|-|-|-|\n|UCB-Hoeffding|$O(\\sqrt{H^4SAT\\iota})$|$\\infty$|$O(H^6C_g)$|$O(T/H)$|\n|UCB-Bernstein|$O(\\sqrt{H^3SAT\\iota}+\\sqrt{H^9S^3A^3\\iota^4})$|$\\infty$|❌|$O(T/H)$|\n|UCB2-Hoeffding|$O(\\sqrt{H^4SAT\\iota})$|$\\infty$|❌|$O(H^3SA\\log T)$|\n|UCB2-Bernstein|$O(\\sqrt{H^3SAT\\iota}+\\sqrt{H^9S^3A^3\\iota^4})$|$\\infty$|❌|$O(H^3SA\\log T)$|\n|UCB-Advantage|$O(\\sqrt{H^2SAT\\iota^3}+H^8S^2A^{\\frac{3}{2}}T^{\\frac{1}{4}})$|$[S^6A^4H^{28},\\infty)$|$O^\\star((\\mathbb{Q}^\\star+\\beta^2H)H^3C_g)$|$O^\\star(H^2S\\log T)$|\n|Q-EarlySettled-Advantage|$O(\\sqrt{H^2SAT\\iota^4}+H^6SA\\iota^3)$|$[SAH^{10},\\infty)$|$O^\\star((\\mathbb{Q}^\\star+\\beta^2H)H^3C_g)$|$O(T/H)$|\n|Ours|$O(\\sqrt{H^2SAT\\iota^2}+H^6SA\\iota^2)$|$[SAH^{10},\\infty)$|$O^\\star((\\mathbb{Q}^\\star+\\beta^2H)H^3C_g)$|$O^\\star(H^2\\log T)$|\n\n\n**Table 2: Comparison of model-free online FRL algorithms.**\n|Algorithm|Worst-case regret|Burn-in cost|Gap-dependent regret|Communication cost|\n|-|-|-|-|-|\n|FedQ-Hoeffding|$O(\\sqrt{MH^4SAT\\iota}+MH^4SA\\iota^2)$|$\\infty$|$O^\\star(H^6C_g)$|$O^\\star(H^2\\log T)$|\n|FedQ-Bernstein|$O(\\sqrt{MH^3SAT\\iota^2}+M\\sqrt{H^9S^3A^3}\\iota^2)$|$\\infty$|$O^\\star(H^6C_g)$|$O^\\star(H^2\\log T)$|\n|FedQ-Advantage|$O(\\sqrt{MH^2SAT\\iota^3}+MH^{7}S^{2}A^{\\frac{3}{2}}\\iota^2)$|$[MS^3A^2H^{12},\\infty)$|❌|$O(MH^2SA\\log T)$|\n|Ours|$O(\\sqrt{MH^2SAT\\iota^2}+MH^{6}SA\\iota^2)$|$[MSAH^{10},\\infty)$|$O^\\star((\\mathbb{Q}^\\star+\\beta^2H)H^3C_g)$|$O^\\star(H^2\\log T)$|\n\n>### **Weakness 1 part 2 and Question 2:  Additional comparison with FedQ-Advantage**\n\nTheoretically, for sufficiently large $T$, our algorithm achieves a switching/communication cost of $O(H^2\\log T)$, which improves upon the $O(H^2S\\log T)$ cost of UCB-Advantage [106] and the $O(MH^2SA\\log T)$ cost of FedQ-Advantage [109]. \n\nEmpirically, to evaluate the switching/communication cost of different algorithms, we plot the average regret per episode, defined as\n$\\text{Regret}(T)/(MT)$, against the policy switching cost in single-agent RL or the number of rounds in FRL. \n\nSpecifically, to show our results, we choose a set of average regret thresholds $\\\\{0.5,0.3,0.1,0.05,0.03,0.01\\\\}.$ For each algorithm, we conduct 10 independent trials and report the median policy switching cost for single-agent RL or median number of communication rounds for FRL required for average regret to fall below each threshold. All evaluations are conducted in the two synthetic environments described in Appendix B, denoted by Settings I-II for single-agent RL and III-IV for FRL. The table below summarizes the results (rounded to the nearest integer), where “None” indicates that the algorithm did not reach the target average regret within the allotted number of episodes.\n\n**Table 3: Median policy switching cost (settiing I and II) or number of rounds (settiing III and IV) required to reach each average regret.**\n|Setting|Algorithm|0.5|0.3|0.1|0.05|0.03|0.01|\n|-|-|-|-|-|-|-|-|\n|I|UCB-Advantage|50|243|608|734|801|902|\n| |Ours|32|149|471|576|633|702|\n|II|UCB-Advantage|10345|13954|15773|17131|None|None|\n| |Ours|8767|11650|12711|13300|13661|None|\n|III|FedQ-Advantage|1063|1230|1608|1704|1768|1867|\n| |Ours|919|1000|1105|1152|1181|1229|\n|IV|FedQ-Advantage|13986|17059|20586|21908|22603|23395|\n| |Ours|10516|12316|14231|15098|15566|16357|\n\nThese results demonstrate that, to achieve any given average regret, our algorithm incurs a lower policy switching cost than UCB-Advantage in single-agent RL, and requires fewer communication rounds than FedQ-Advantage in FRL.\n\n>### **Weakness 2: Technical novelty**\n\nWe appreciate the opportunity to clarify our novelty. Our work does not simply combine prior techniques. Instead, we have developed novel analytical tools that go beyond prior work. Appendix C provides a detailed discussion of the challenges and our corresponding contributions. Our novelty and contribution lie in addressing non-trivial theoretical and algorithmic challenges that arise when combining their respective strengths.\n\nThe reference-advantage decomposition, suffers from non-adaptiveness in both weights and reference functions when applied in a round-based setting, especially under communication constraints. We propose a new decomposition that uses **surrogate reference functions**, enabling tighter worst-case regret bounds while avoiding reliance on empirical process techniques that result in an additional factor of $\\log T$.\n\nWe also introduce a **new two-sided variance bound** to tighten regret under delayed updates in the proof of the optimism property ($Q_h^k\\geq Q_h^\\star$, Lemma H.1). Specifically, we derive both upper and lower bounds on the variance estimator (Eq. 33, 37, 38), whereas prior works (such as [48]) only use the lower bound. This refinement leads to more accurate confidence intervals in parts (b) and (c) of Lemma G.1 and allows us to improve the bonus term $\\beta_h^R$ in the reference-advantage decomposition, reducing the cumulative bonus and yielding both tighter regret and better empirical performance.\n\nFurther, we leverage the **Lower confidence bound** to trigger early reference settling. Unlike the single-agent setting, our method adopts a different design in the early and late rounds to integrate the LCB-based strategy with round-based synchronization, ensuring low switching and communication costs. This approach is formalized in Equations (10) and (14), which help bound the reference settling error in Lemma H.4 and contribute to reducing the burn-in cost—a benefit that prior FRL methods (e.g., FedQ-Advantage) cannot achieve.\n\nFinally, in the FRL setting, integrating these techniques involves new challenges in synchronizing learning progress across agents, managing reference settling in a distributed and delayed-update setting, and maintaining both low communication cost and low switching cost.\n\n>### **Question 1: Notation** \n\nThank you for the advice! We will correct this notation accordingly in the revised manuscript.\n\n>### **Question 3: Key to reduce burn-in cost**\n\nOur work improves upon FedQ-Advantage by addressing key sources of estimation error that contribute to the burn-in cost. Specifically:\n\n**LCB-Based Reference Settling.** Our algorithm introduces an LCB-type estimate $Q_h^{\\text{L},k}$ to control the reference settling error more tightly in Lemma H.4. This reduces dependence on $H,S,A$, leading to a lower burn-in cost.\n\n**Two-Sided Inequality for Tighter Bonuses.** As discussed in our response to Weakness 1 part 2, we use a new two-sided inequality to refine the reference-advantage bonus, yielding tighter confidence bounds and more accurate $Q$-estimates, which directly contribute to improved regret and reduced burn-in cost.\n\n**Surrogate Reference Functions.** We further reduce the burn-in by introducing surrogate reference functions, which address the non-adaptiveness of both the weights and the reference functions in the regret decomposition. This innovation improves the tightness of the analysis and avoids the inefficiencies associated with empirical process techniques used in earlier works.\n\nTogether, these contributions enable our algorithm to achieve lower burn-in costs while maintaining strong regret and cost guarantees, marking a significant improvement over FedQ-Advantage.\n\n>### **Question 4: Visualizing the burn-in costs**\n\nThank you for the helpful suggestion. We conducted additional experiments under the two synthetic environments described in Appendix B, denoted by Settings I-II for single-agent RL and III-IV for FRL. To evaluate the burn-in cost of different algorithms, we plot the normalized regret curves\n$$\\frac{\\text{regret}(t)/\\log(t+1)}{\\text{regret}(N)/\\log(N+2)},$$where $N = T/H$ denotes the total number of episodes per agent. By examining these curves, we observe that, our algorithm consistently requires the smaller number of episodes than all baseline methods to achieve the same normalized regret level.\n\nTo show the results, we select a set of normalized regret thresholds $\\\\{0.5,0.8,0.85,0.9,0.95,0.99\\\\}.$ For each algorithm, we conduct 10 independent trials and report the median number of episodes per agent needed to reach or exceed each threshold. As shown in the following table, our method achieves lower burn-in cost and superior sample efficiency.\n\n**Table 4: Median number of episodes per agent required to reach each normalized regret.**\n|Setting|Algorithm|0.5|0.8|0.85|0.9|0.95|0.99|\n|-|-|-|-|-|-|-|-|\n|I|UCB-Advantage|3467|14459|20045|28541|44776|89882|\n| |Q-EarlySettled-Advantage|4130|20649|28355|43044|72082|139783|\n| |Ours|1453|7241|9821|13687|23122|44861|\n|II|UCB-Advantage|47905|395867|574937|848694|1285514|1628711|\n| |Q-EarlySettled-Advantage|93015|587867|786596|1063962|1478185|1884091|\n| |Ours|38335|131755|181790|272172|505089|841384|\n|III|FedQ-Advantage|420|2266|3074|3646|5786|10078|\n| |Ours|151|837|1099|1551|2336|3770|\n|IV|FedQ-Advantage|13694|64988|85668|112999|149730|229123|\n| |Ours|4389|18868|26872|41243|74978|132901|\n\n(All reference numbers are from our paper.)"}, {"review_id": "vvWcOeBiBP", "reviewer": "Reviewer_wTVm", "summary": "This paper addresses the challenge of designing model-free reinforcement learning (RL) algorithms that are both sample-efficient and communication-efficient. In both single-agent and federated RL settings, existing methods either require large burn-in costs or incur frequent policy switching or communication. To mitigate this issue, this paper proposes two new algorithms: Q-EarlySettled-LowCost for single-agent RL and FedQ-EarlySettled-LowCost for federated RL. These are the first model-free methods to simultaneously achieve near-optimal regret, burn-in costs that scale linearly with the number of states and actions, and only logarithmic switching or communication costs.\n\nThe key idea seems to be the combination of a round-based learning structure with the classic LCB techniques, enabling infrequent updates without sacrificing learning efficiency. The algorithms outperform existing state-of-the-art methods by reducing the switching or communication overhead while maintaining low regret. In the theoretical aspect, the paper gives strong gap-dependent performance guarantees. In terms of technical novelty, the paper introduces new analytical tools to handle technical challenges in regret analysis. Overall, the paper provides practical and theoretically reliable solutions for efficient RL in settings where data collection or communication is costly.", "questions": "Do you think this result can be extend to general cases with continuous state and action space (such as MDP with function approximation)?", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "**Quality**\n\nStrengths:\n\n1, Theoretically Rigorous: The paper provides tight worst-case and gap-dependent regret bounds for both single-agent and federated reinforcement learning (FRL), matching or improving over existing results. The analysis incorporates nontrivial techniques (e.g., surrogate reference functions, LCB-based early settlement). In terms of technical novelty, the analysis successfully handles double non-adaptiveness, a nontrivial technical barrier in FRL.\n\n2, Algorithmic Soundness: The proposed algorithms—Q-EarlySettled-LowCost and FedQ-EarlySettled-LowCost—are well-motivated and robustly designed. Their use of refined bonuses and structured policy updates yields practical and theoretical benefits. The numerical experiments confirm the regret and cost improvements over strong baselines, including UCB-Advantage and FedQ-Advantage.\n\n**Clarity**\n\nStrengths:\n\n1, I think this paper has good clarity in general. The problem is clearly defined. The similarity and difference from existing works in federated RL is well described in detail. Technical novelty is explicitly mentioned. \nI also really appreciate the illustration in Appendix D, which makes it easier for the reader to understand the federated RL framework which is quite complicated to be honest.\nOther good practices include: Table 1 and 2 provide a clear comparison with existing methods. \n\nThe only issue is that the notation is a bit heavy (for example, page 6). But I think this is just a minor issue and given the theoretical nature and complexity of the federated RL problem setting, I do not think there is a significantly better way to present the theoretical results.\n\n**Significance**\n\nStrengths:\n\n1, Addresses a Key Challenge in FRL: Communication and synchronization costs are one of the key problems in Federated RL. The proposed algorithms directly address these issues with provable logarithmic cost.\n\n\n**Originality**\n\n1, I think the major novelty of the paper is its technical improvement. Specifically, I think the successful adaptation of the existing surrogate reference functions to worst-case regret framework is one of the major originalities. This is an advancement in the field of statistical methodology, which can potentially have broader applicability in not only federated learning but other problem settings as well.\n\n**Minor Weaknesses**\nOn the empirical side, only very simple numerical experiments have been conducted. \nNotation is a bit heavy. \nA lack of proof sketch in the main text (there is, though, in Appendix K).", "was_revised": true, "final_justification": "I thank the authors for their initial rebuttal and follow-ups.\n\n1. The authors have addressed my concern by  incorporated suggested refinements and discussed extensions to the more general setting of continuous state and action space.\n\n2. Regarding the points raised by other reviewers, I think the authors have done a good job at (i) clarifying the comparison with existing algorithm, (ii) emphasis on the technical novelty of the paper.\n\nGiven these information, I think this is a good paper and thus I maintain my score at 5 and recommend for acceptance.\n\nGood luck!", "rebuttal": "We thank you for your careful reading and thoughtful comments. Below are our point-by-point responses to your questions, and we hope our responses address your concerns.\n\n>### **Weakness 1: Simple numerical experiments**\n\nWe have conducted additional experiments to demonstrate the reduced communication cost and low burn-in cost compared to other baselines.\n\n**Additional Experiment 1: Comparison of switching cost with UCB-Advantage [1] and the number of communication rounds with FedQ-Advantage [2]**\n\nTo evaluate the switching/communication cost of different algorithms, we plot the average regret per episode, defined as\n$\\text{Regret}(T)/(MT)$, against the policy switching cost in single-agent RL or the number of rounds in FRL. \n\nSpecifically, to show our results, we choose a set of average regret thresholds $\\\\{0.5,0.3,0.1,0.05,0.03,0.01\\\\}.$ For each algorithm, we conduct 10 independent trials and report the median policy switching cost for single-agent RL or median number of communication rounds for FRL required for average regret to fall below each threshold. All evaluations are conducted in the two synthetic environments described in Appendix B, denoted by Settings I-II for single-agent RL and III-IV for FRL. The table below summarizes the results (rounded to the nearest integer), where “None” indicates that the algorithm did not reach the target average regret within the allotted number of episodes.\n\n**Table 1: Median policy switching cost (settiing I and II) or number of rounds (settiing III and IV) required to reach each average regret.**\n|Setting|Algorithm|0.5|0.3|0.1|0.05|0.03|0.01|\n|-|-|-|-|-|-|-|-|\n|I|UCB-Advantage|50|243|608|734|801|902|\n| |Ours|32|149|471|576|633|702|\n|II|UCB-Advantage|10345|13954|15773|17131|None|None|\n| |Ours|8767|11650|12711|13300|13661|None|\n|III|FedQ-Advantage|1063|1230|1608|1704|1768|1867|\n| |Ours|919|1000|1105|1152|1181|1229|\n|IV|FedQ-Advantage|13986|17059|20586|21908|22603|23395|\n| |Ours|10516|12316|14231|15098|15566|16357|\n\nThese results demonstrate that, to achieve any given average regret, our algorithm incurs a lower policy switching cost than UCB-Advantage in single-agent RL, and requires fewer communication rounds than FedQ-Advantage in FRL.\n\n**Additional Experiment 2: Burn-in cost comparison**\n\nWe also conducted additional experiments for burn-in cost under the two synthetic environments described in Appendix B, denoted by Settings I-II for single-agent RL and III-IV for FRL. To evaluate the burn-in cost of different algorithms, we plot the normalized regret curves\n$$\\frac{\\text{regret}(t)/\\log(t+1)}{\\text{regret}(N)/\\log(N+2)},$$\nwhere $N = T/H$ denotes the total number of episodes per agent. By examining these curves, we observe that, our algorithm consistently requires the smaller number of episodes than all baseline methods to achieve the same normalized regret level.\n\nTo show the results, we select a set of normalized regret thresholds $\\\\{0.5,0.8,0.85,0.9,0.95,0.99\\\\}.$ For each algorithm, we conduct 10 independent trials and report the median number of episodes per agent needed to reach or exceed each threshold. As shown in the following table, our method achieves lower burn-in cost and superior sample efficiency.\n\n**Table 2: Median number of episodes per agent required to reach each normalized regret.**\n|Setting|Algorithm|0.5|0.8|0.85|0.9|0.95|0.99|\n|-|-|-|-|-|-|-|-|\n|I|UCB-Advantage|3467|14459|20045|28541|44776|89882|\n| |Q-EarlySettled-Advantage|4130|20649|28355|43044|72082|139783|\n| |Ours|1453|7241|9821|13687|23122|44861|\n|II|UCB-Advantage|47905|395867|574937|848694|1285514|1628711|\n| |Q-EarlySettled-Advantage|93015|587867|786596|1063962|1478185|1884091|\n| |Ours|38335|131755|181790|272172|505089|841384|\n|III|FedQ-Advantage|420|2266|3074|3646|5786|10078|\n| |Ours|151|837|1099|1551|2336|3770|\n|IV|FedQ-Advantage|13694|64988|85668|112999|149730|229123|\n| |Ours|4389|18868|26872|41243|74978|132901|\n\n\n>### **Weakness 2: Notation is a bit heavy** \n\nThank you for the suggestion. To improve clarity and ease of reference, we have included two notation summary tables for our algorithms in Appendix D.2 of the original submission.\n\n>### **Weakness 3: A lack of proof sketch in the main text** \n\nThank you for the suggestion. Due to space constraints, we did not include the proof sketch in the main text of the original submission. However, we will incorporate a key proof sketch into the main text using the additional page provided for the revised manuscript.\n\n>### **Question: Extension to general cases with continuous state and action space**\n\nThank you for the insightful question. Extending FedQ-EarlySettled-LowCost to non-tabular settings, such as those involving continuous state/action spaces or linear function approximation, is a promising but nontrivial direction for future work.\n\nRecent works have explored related ideas in the offline RL setting. For example, [3] proposes a federated offline RL algorithm using confidence-bound methods, while [4, 5] apply reference-advantage decomposition techniques in offline RL with linear function approximation. These works demonstrate the feasibility of using confidence bounds and reference-advantage decomposition techniques in non-tabular environments. \n\nHowever, adapting our event-triggered termination mechanism to non-tabular settings presents significant challenges. For environments with continuous state spaces, it becomes difficult to quantify visitation counts, the design of stopping conditions for exploration becomes ambiguous, and policy updates based on event-triggered signals must be carefully coordinated across agents become complex, especially under communication cost constraints. These challenges in the online RL and online FRL settings require new algorithmic and theoretical tools. We agree with you and view this as an important direction for future work.\n\n[1] Zihan Zhang, Yuan Zhou and Xiangyang Ji. Almost optimal model-free reinforcement learning via reference-advantage decomposition. NeurIPS 2020.\n\n[2] Zhong Zheng, Haochen Zhang and Lingzhou Xue. Federated Q-learning with reference advantage decomposition: Almost optimal regret and logarithmic communication cost. ICLR 2025.\n\n[3] Doudou Zhang, Yufeng Zhang, Aaron Sonabend-W, Zhaoran Wang, Junwei Lu and Tianxi Cai. Federated offline reinforcement learning. Journal of the American Statistical Association, 2024.\n\n[4] Wei Xiong, Han Zhong, Chengshuai Shi, Cong Shen, Liwei Wang and Tong Zhang. Nearly Minimax Optimal Offline Reinforcement Learning with Linear Function Approximation: Single-Agent MDP and Markov Game. ICLR, 2023.\n\n[5] Qiwei Di, Heyang Zhao, Jiafan He and Quanquan Gu. Pessimistic Nonlinear Least-Squares Value Iteration for Offline Reinforcement Learning. ICLR, 2024"}]

Author rebuttal:

Meta-review: Online RL (and federated RL) algorithms are designed with near-optimal regret, low (linear in S, A) burn-in costs and logarithmic policy switching/communication cost. The main technical challenge lies in achieving the latter two simultaneously.
The result is a lengthy analysis that requires combining and adapting several advanced (existing) techniques with great care. The reviewers agree that the paper is sound and clear. The crucial question is whether it is incremental in nature.
The discussion was not enough to dismiss the impression that the problem the authors set themselves to solve is rather artificial. Experiments were appreciated (with some doubts regarding scalability). However, neither these, nor the appeals to motivating practical settings, nor the reiteration of the fine technical solutions needed to achieve all of these theoretical guarantees simultaneously, seemed to budge the reviewers from their initial impression of incrementality.
However, given the intrinsic value of the theoretical analysis I confirm the positive evaluation maintained by most reviewers.
Decision: Accept (poster)