Federated $Q$-Learning with Reference-Advantage Decomposition: Almost Optimal Regret and Logarithmic Communication Cost
Authors: Zhong Zheng
Haochen Zhang
Lingzhou Xue
Venue: ICLR 2025 Poster (2025)
Keywords: Federated Learning
Reinforcement Learning
variance reduction
communication cost
Primary area: reinforcement learning
TL;DR: This paper designs a federated Q-learning algorithm with variance reduction and reaches an almost optimal regret and a logarithmic communication cost.

Abstract: In this paper, we consider model-free federated reinforcement learning for tabular episodic Markov decision processes. Under the coordination of a central server, multiple agents collaboratively explore the environment and learn an optimal policy without sharing their raw data. Despite recent advances in federated $Q$-learning algorithms achieving near-linear regret speedup with low communication cost, existing algorithms only attain suboptimal regrets compared to the information bound. We propose a novel model-free federated $Q$-Learning algorithm, termed FedQ-Advantage. Our algorithm leverages reference-advantage decomposition for variance reduction and adopts three novel designs: separate event-triggered communication and policy switching, heterogeneous communication triggering conditions, and optional forced synchronization. We prove that our algorithm not only requires a lower logarithmic communication cost but also achieves an almost optimal regret, reaching the information bound up to a logarithmic factor and near-linear regret speedup compared to its single-agent counterpart when the time horizon is sufficiently large.

Published as a conference paper at ICLR 2025
FEDERATED Q-LEARNING WITH REFERENCE- ADVANTAGE DECOMPOSITION: ALMOST OPTIMAL REGRET AND LOGARITHMIC COMMUNICATION COST
Zhong Zheng, Haochen Zhang Lingzhou Xue
Department of Statistics The Pennsylvania State University
State College, PA, 16802, USA
(zvz5337, 12v25337,hg225340 zxue @psu.
ABSTRACT
this paper, we consider model-free federated reinforcement learning for tabular episodic Markov decision processes. Under the coordination of a central server, multiple agents collaboratively explore the environment and learn an optimal policy without sharing their data. Despite recent advances in federated Q-leaming algorithms achieving near-linear regret speedup with low communication cost, existing algorithms only attain suboptimal regrets compared to the information bound. We propose a novel model-free federated Q-learning algorithm, termed FedQ-Advantage. Our algorithm leverages reference-advantteg decomposition for variance reduction and adopts three novel designs: separate event-triggered communication and policy switching, heterogeneous communication triggering conditions, and optional forced synchronization. We prove that our algorithm not only requires lower logarithmic communication cost but also achieves an almost optimal regret, reaching the information bound up to logarithmic factor and near-linear regret speedup compared to its single-agent counterpart when the time horizon is sufficiently large.
INTRODUCTION
Federated reinforcement learning (FRI. is distributed learning framework that combines the principles of reinforcement learning (RL) (Sutton & Barto 2018) and federated lcarning (FL) (McMahan et al. 2017). Focusing sequential decision-male making. FRL aims to Iearn optimal policy through parallel explorations by multiple agents under the coordination of a central server. Often modeled Markov decision process (MDP), multiple agents independently interact with an initially unknown environment and collaboratively train their decision-making models with limited information exchange between the agents. This approach accelerates the learning process with low communication costs. Some model-based algorithms (e.g.. Chen et al. (2023)) and policy-based algorithms (c.g.,Faa Fan al. (202T) have shown speedup with respect the number of agents in terms of learning regret or convergence rate. Recent progress has been made in FRL algorithms based on model-free malue-based approaches, which directly learn the value functions and the optimal policy without estimating the underlying model (e.g.. Woo et al. (2023)). However, limiting our focus to tabular MDPs, most existing model-free federated algorithms do not actively update the exploration policies for local agents and fail to provide low regret. A comprehensive literature review is provided in Appendix
1.1 FEDERATED Q-LEARNING: PRIOR WORKS AND LIMITATIONS
In this paper, focus model-free FRL based on the classic Q-leaming algorithm (Watkins, 1989 tailored for episodic tabular MDPs with inhomogeneous transition kernels. Specifically, we assume the presence of a central server and M local agents in the system. Each agent interacts independently with an episodic MDP consisting of states, A actions, and H steps per episode.
*7. Zheng and H. Zhang co-first authors. I., Xue the corresponding author.

---

Published as a conference paper at ICLR 2025
Let T denote the number of steps for each agent. Under the single-agent setting of the episodic MDP, Domingues et al. (2021) and Jin et al. (2018) established a lower bound for the expected total regret of HATT), An algorithm considered almost optimal when achieves a regret upper bound of (O have been shown be almost optimal. Research on provably efficient model-free algorithms began with et al. (2018) and was further advanced by Bai et al. (2019); [Zhang et al. (2020); Li et al.
for large values of T. Multiple
algorithms (e.g., Zhang et al. (023))
(2021). Specifically, Zhang et al. (2020); Li et al. (2021) proposed almost optimal algorithms that utilized reference-ad vanatage decomposition for variance reduction.
For the federated setting, the information bound naturally translates to D2( H2SAMT), allowing us to define almost optimal federated algorithms similarly. However, the literature on federated model-free algorithms is quite limited. [Bai et al. (2019) and and Zhang al. (2020) proposed concurrent algorithms where multiple agents generate episodes simul Iunuouuny and share their original data with the central server. These designs achieved low policy-switching costs (VV
and DVHHSSAV respectively but incurred a high communication cost of ((MT). Zheng et al. (024a) proposed federated algorithms with near-linear regret speedup compared to Jii et al. (2018) and Bai et al. (2019) and logarithmic communication cost, but they only achieved a suboptimal regret of O(v M This raises the following question:
possible to design an almost optimal federated model-free RI. algooritn that enjoys logarithmic communication cost?
1.2 SUMMARY OF OUR CONTRIBUTIONS
We answer this question affirmatively by proposing the FedQ-Advantage algorithm achieve the almost optimal regret and the logarithmic communication cost. Our contributions are summarized below.
Algorithmic design. In FedQ-Advantage, the server coordinates the agents by actively updating their policies, while the agents execute these policies. collect trajectories, and periodically share local aggregations with the server. We adopt upper confidence bounds (UCB) to promote exploration and use the reference-advantage decomposition when updating the Q-function. The algorithm design incorporates the following key elements that crucial for achieving near-optimal regret.
(1) Aligned round-wise communication and unaligned stage-wise updates. We design new mechanism based on event-triggered communication and policy switching, both of which are triggered when specific conditions are satisfied. This structure divides the learning process into aligned communication rounds, which are grouped into stages. These stages are unaligned across different stateacction-see step tuples. Communication takes place after each round, while policy switching occurs only at the end of each stage. This mechanism employs the unaligned stage design from Zhang et al. (2020), which is not used in Zheng al. (2024a). During communication. local agents share the round-wise aggregated sums of function values over visits to each tuple rather than entire trajectories. The central server then constructs global estimates within the reference- add advataeee decomposition framework, maintaining low communication costs.
(2) Heterogeneous event- went-triggered Communication. An agent terminates its exploration and requests communication in round when the number of visits to any state-action-step tuple reaches a threshold, which guarantees sufficient exploration under restrictions. We adopt a heterogeneous design for the threshold that encourages more visits in the early rounds of stage and limits the visits in later rounds to form desired stage renewals. This differs from the condition in Zheng et al.) (2024a) that always poses strict limits.
(3) An optional forced synchronization mechanism. Under this mechanism offered by FedQ- Advantage, when one agent triggers the communication condition, the central server terminates the exploration for all agents and initiates heterogeneity in agents' exploration speeds and eliminates waiting time. In the absence of forced synchronization, the central server waits for each agent to individually meet the communication condition, thereby reducing the number of communication rounds required.
round. This approach enhances robustness to
IÔ hides logarithmic factors.
2

---

Published as a conference paper at ICLR 2025
Table Comparison of regrets and communication costs for multi-agent RL algorithms.
Type
Algorithm (Reference)
Regret
Communication cost
Multi-butch RL (Zhang et al.. 2022
O(VI=SAMM)
Model-bused
APEVE Qiao et al 2022
O(VIIASAMM)
Byzan-UCBVI Chen et 2023
O(VIPSPAMT)
Concurrent Q-UCB2H
(Bai et al. 2019
SAMHT)
O(MT) ((MT)
Concurrent Q-UCB2B (Bai et al. 2019
SAMTT
Model-free
Concurrent UCB- Advantage Zhanng al.
2020
O(VH
O(MT)
FedQ Heai--Heefdding Zheng et 2024a
OSAHSSAMT
O HAS Aog
FedQ-Bernster (Zheng el 2024a
O(VH'SAMT
O log
(this work)
Of MH Allog H) log T)
H: number steps per episode; T: lotal number steps; S: number of stallss A: number of actions: M: mumber of agents, i; not discussed. I'r equals to M the forced synchronization design used and equals else.
Performance guarantees. FedQ-AAvantagee provably achieves an almost optimal regret and near near-linear& speedup in the number of agents compared with its single-agent counterparts (Zhang ct al. 2020) when T' is sufficiently large. The regret bound holds regardless of whether forced synchronization used. Its communication cost scales logarithmically with T,, outperforming the federated algorithms in Zheng al. (2024a) and matching the policy switching cost in Zhang et al. (2020), which is the best cost for Q-learning in the literature. To the best of our knowledge, is the first model-free federated RL algorithm to achieve almost optimal regret with logarithmic communication cost. We compare the regret and communication costs under multi-agent tabular episodic MDPs Table I Numerical experiments also demonstrate that aad--Advatagee has better regret and communication cost compared to the federated algorithms in Zheng et al. (2024a).
Technical novelty. We highlight two technical contributions here. (1) Stage-wise approximations in non-martingale analysis. The event-triggered stage renewal presents non-trivial challenge involving the concentration of the sum of non-martingale difference sequences. The weight assigned to each visit of given tuple (s, a, h) depends on the total number of visits between two model aggregation points, which is not causally known during the visitation. This paper proves the concentration by relating the sequence to a martingale difference sequence and bounding their stage-wise gap, which is different from Woo et al. (2023) and Woo et al. (2024) that used static behavior policies and bound similar gaps element-wisely. Our approach does not rely on a stationary visiting probability or the estimation of visiting numbers. (2) Heterogeneous triggering conditions for synchronization. For different rounds (of synchronization) policy update), we use different triggering conditions that allow more visits of tuple (s, a, h) in early rounds. This reduces the number of synchronizations within a stage to Offs log H) from Df which would occur under homogeneous triggering conditions in Zheng et al. (2024a). This is key to improving the communication cost of Zheng et al. (2024a) and matching the policy switching cost of Zhang et al. (2020).
a given stage (of
The rest of this paper is organized as follows. Section 22 provides the background and problem formulation. Section 3 presents the algorithm design of FedO-Advantage. Section 4 studies the performance guarantees in terms of regret and communication cost. Section concludes the paper. Related works, proofs, numerical experiments, and more details are presented in the appendices.
BACKGROUND AND PROBLEM FORMULATION
2.1 PRELIMINARIES
We first introduce the mathematical model and background on Markov decision processes. Through- out this paper, we assume that 0/0 = O. For any C' E N. we use [C]] to denote the set {1, 2,, 2.... C'). We use [[x] to denote the indicator function, which equals when the event is true and 0 otherwise.
Tabular episodic Markov decision process (MDP). A tabular episodic MDP is denoted as M := (S,A, r,), where S is the set of states with | S,A is the set of actions with |A| = A, H the number of steps in each episode, IP == {F,, /7 /=1 is the transition kernel so that (. s, characterizes the distribution over the next state given the state action pair (s, a) at step h, and
3

---

Published as a conference paper at ICLR 2025
r: (ra is the collection of reward functions. We assume that ra a) E [0. 1] is deterministic function of a), while the results can be easily extended to the case when 7/2 is random.
In each episode of M, an initial state 81 is selected arbitrarily by an adversary. Then, at each step h E [H]] an agent observes a state 8/ E S, picks an action dn E A. receives the reward rh rm (52, (h) and then transits the next state 81+1- The episode ends when absorbing state SH++ is reached. Later on, for the ease of presentation, we use "for any (A) (s, a, h)" to represent "for PPPssePPallle (5h+1))
any (4) (s. h) E E x A x [H]" and denote P. Ps.a. and 1, [(s),, V(s, a, for any function f : R.
5, an a)
Policies, state value functions, and action value functions. A policy т is a collection of H functions { S A ne(ny where A is the set of probability distributions over A. A policy deterministic if for any E S, (s) concentrates all the probability mass on an action E A. In this case, we denote (s) a.
Let V : S + R and Q7 S x - R denote the state value function and the action value function at step h under policy Mathematically, V7 (s) Σn= (es [T (sp' (xx) 8h. =]. Oh = a]. Since
We also use Q7 (8, a) : (s a) + (s,,,,,,, ()) (<(,.)) [Tw (sw: ) 8%
the state and action spaces and the horizon are all finite, there always exists an optimal policy nf that
achieves the optimal value (s) sup, Vi(s) (s) V/," (s) for all S and h [H] (Azar et al. 2017). The Bellman equation and the Bellman optimality equation can be expressed as
(s) (u'==,())) (7) (s, = (s, a) - Ps,an Vitt1 and {
(s) max (s, ())s.)) = (s, a) + + Paahh Vit11 (++ 0, a(s,a,))
(I)
V (5) 0, a),
2.2 THE FEDERATED RL FRAMEWORK
We consider an FRL setting with a central server and M agents, each interacting with an independent copy of M. The agents communicate with the server periodically: after receiving local information, the central server aggregates it and broadcasts certain information to the agents to coordinate their exploration. We assume that the central server knows the reward functions (ra)h=1 beforehand" We define the communication cost of an algorithm as the number of scalars (integers or real numbers) communicated between the server and agents similar to Zoennng et al./ (2024a).
For agent m, let Um be the number of generated episodes, n., be the policy in the u-th episode, and $1 sm. be the corresponding initial state. The regret of M agents over T H > Um total steps is
U
Regret( (T) = Σ
VI
VIT" (
mE [M]] am1
Here, 7 := f/M is the average total steps for M agents.
3 ALGORITHM DESIGN
In this section, we elaborate on our model-free federated RL algorithm termed FedQ-Advantage.
3.1 BASIC STRUCTURE: ALIGNED ROUNDS AND UNALIGNED STAGES
We first review the single-agent algorithm in Zhang et al. (2020). The agent generates episodes and
splits them into stages for each (s, a, h). Denoting 1/1 (8, a, h) as the number of visits (s, a, h) in
the f-th stage for (s, a, h), it requires that (s, a. h) = [11 + H/HH)ybss, estimated Q-functions (s, a, h) only happen at the end of each stage. Due the randomness of the visits, stage renewals for different triples might not happen simultaneously, resulting in unaligned
h)], and the updates of
stages. The exponential increase of the stage size leads to a low policy switching cost: the number of
TTo handle unknown reward functions, we only need slightly modify algorithm to let agents share this information. This will not affect Theorems and 4.2 regret and communication cost.
4

---

Published as a conference paper at ICLR 2025
different implemented policies is upper bounded by OHH T). This provides the potential to parallelize the episodes generated under the same policy to multiple agents.
However, the simple design in Zheng ct al. (2024a) does not accommodate the unaligned stages. Thus, FedQ-Advantage designs novel aligned rounds for unaligned stages. Next, we introduce our algorithm design, which is also visually shown in Figure It proceeds in rounds indexed by A [K] and agent m generates n= episodes in round k. The communication between agents and the central server occurs the end of each round. For each (s, a, h). we divide rounds E [K] into stages Each stage contains consecutive multiple rounds: denote kij (s, a) as the index of the first round that belongs to stage t, so kj, < k/,t1, and stage t is composed of rounds kj,, ki + I,..., A 1. Note that the definition of stages is specific to (s, a, ht). meaning that given round may belong to different stages for different (s, h). Each round equips the agents with a common policy n² for independent
1, 2,... .....
explorations and an event-triggered termination condition that will be explained later. At the end of each round, state renewal is judged for each (s, a, h) separately, resulting in unaligned stages.
(s 20,a", h+)
Stage 1
Stage 2
Stage Ti
1
2
k1
h12
K
K rounds
1
112
hz22
(s² a², h2a)
Stage 1
Stage 2
Stage T2
Figure 1: The relationship between rounds and stages for different triples (s , and (s², a² 112). Each square represents a round, and the number inside indicates the round index. stage is composed of consecutive rounds. Communication occurs at the end of each round and the estimated Q-function is updated at the end of each stage. We can find from the figure that a round may belong to different stages for different triples. For example, the round kn is in stage 1 of (s' a h'), while in stage 2 of (s² a,,,a², (2).. Here, ky k (s', .a) represents the index of the last round in stage t for (s' a², Nt), t
} and i E (1,2). Ti and T2 the total number of stages for (s a. hh") and (s² 02,,a, h²) respectively.
FedQ Advantage updates the estimated Q-function at (s, a, h) only at the end of each stage using stage-wise global mean values regarding the next states of visits to (s, a, f). Thus, agents only need to prepare and share corresponding local round-wiss means for global aggregations. It results in an (S) communication cost within each round that is independent of the number of episodes.
3.2 ALGORITHM DETAILS
We provide a notation table in Appendix A to facilitate understanding of this section. For the j-th (j E ()) episode in the k-th round, let s1 k.m.j be the initial state for the m-th agent, and [(5). k.m.j k.m.j k.m. H } Jj== be the corresponding trajectory. Define {V/ S + R]
ap .hh
(Q), S x A R] and [Vret S R] as the estimated V-function, the estimated Q-function and the reference function at the beginning of round k. Here, Q% V V 0.
We use / v 4
Vk veel denote the estimated advantage function. For any predefined functions S x A R or f: S + R. we will use g or f in replace of g(s, a) or f(s) when there is no ambiguity for simplification. We also denote (s,, a) as the stage index round k and gren.k (s, a) = 11th - as stage renewal indicator with 1eem = 1, V(s, a, ft).
Then we briefly explain each component of the algorithm in round k as follows.
Step 1. Coordinated exploration for agents. At the beginning of round k the server holds the n values on all states, actions, and steps for functions (Q), Vž. Vrre&& No.. n ahj. Here, N7 (s, a) is the total number of visits for all agents up to but not including stage th n (s, is the total number of visits for all agents in the stage 1%: - 1, and (s a) is the number of visits for all the agents in the stage th before the start of round k. Here, n = 0 if th = 1. When k = 1, Qh. V/
H, V(s, h) and nt is an arbitrary deterministie policy. It also holds
5

---

Published as a conference paper at ICLR 2025
( the following global values Ph, (s. a), oh When 1, they are initialized as Further explanations will be provided in their updates in Step 4. Next, the central server decides a deterministic policy N² { // h= and then broadcasts oi along with (s (+)), (s T. (s))),,n and {V,, Vieff ja.n to all the agents. Once receiving such information, the agents will execute policy nh and start collecting trajectories.
adv.k (s. (s. a), oh o a), Mb. (s, a), V(s. a, h). of (s, a), Pn
Step 2. Event-triggered termination of exploration. We introduce Boolean variable Myyn as an input to the algorithm for the forced synchronization. During the exploration under π², every agent will monitor its total number of visits for each (s, a, h) triple within the current round. Define
{ [ a) if n a) > O, ( a) > (1 - 10111H)),,,.000 max (1, (n a) n. (s.,
(0.
(2)
otherwise.
Ueyn = TRUE, for any agent m, at the end of each episode, if any (s, a, h) has been visited by a) times, the agent will stop exploration and send a signal to the server that requests all agents to abort the exploration. If Vagnn = FALSE, the central server will wait until for each agent, there exists triple (s, a, h) that has been visited by (s,, a) times.
J.m. k.m.d During this process, each agent m collect m trajectories {(s) Hmm. ,a -h ) Dimmi. E [m mm and calculates the following local quantities for a (s):
F
m.kk m.k (s, a), m. (s, a), Phaddy (s, a), m.kk (s, a). o m.k (s, a), Ma (s, a). h).
(3)
mm.k (s, a) is the number of visits to (8, a, h) for agent m in round k. Thus, we have Here, n
V(s, h, m. k), ny m.k (s. S ())))),
Vk, 3(s, a, h, m), s.l. n m.kk (s, c (s) if Usyn TRUE
(4)
m.kk Vm, hi (s,,a, h), s.1. my (s, ()) if Usyn = FALSE
(5)
Other quantities correspond to the summation of the values of five different functions applied to the next states of all the visits to (8,a, h) for agent m in round k. These five functions are
veeti 1 K+1 h++1
padv, V [Vref [V Mathematically, for J S - R. letting A Am,,.,, (J) =
Ej=1 f( (.m5)))) x I[(s), m..... a% B.m..)) = (s, a)] as the summation of f on the next states for all the visits to (s, a, 16) for agent m in round k. When there is no ambiguity, we will use the simplified m.k
notation A (f) = A (f)) Then, m.kk (s, a) = A (Vri1)) ah (s, a) = A (Va44)) ) (s, a) = A 11) m., ( = A ([V4et11)) and h. Ra (s,a) a) = 4 ([v These quantities correspond to local aggregations of different types of value functions and can be adaptively calculated when collecting the trajectories as shown in Algorithm 2
Step 3. Stage renewal. After the exploration round k, agents share local quantities in Equation 3
on all (s, a, h) such that a = . (8) to the central server. Then it finds existing visits in stage 1 as
n ( (s,
Σ
m% ms (s, a(s,a,)).
(6)
and renew the stages for triples that are sufficiently visited: V(s a, h),
(8, a) (s) + + n (s, a) 2 (m) 0JMH + (1 (1+1/H)
(7)
In Equation 77p. when n 0. i.e., 1/2 1, the state renewal threshold is M Else, it is
(1+ )/ With Equation 7 the central can determine the stage renewal indicator 1/. jen and the counts N/++1 1 n
k+1 =++ as shown in lines 13 and 18 in Algorithm |
Step 4. Updates of estimated value functions and policies. According to the stage renewal, the
central server updates the global values pel,k ,0h
_ell. udv,k ouul.. pia at all (s, a, h) as follows: .1t ,0t ,1h
ref & + Σ(u, (u, rof, = (u,,))offe (1, ( ())offfft
(8)
m

---

Published as a conference paper at ICLR 2025
(n 110 a (1 11-h Ihe Ai) ( 1a oatt yh +
Σ adv yaly Ch,adv) )m.k
Equation (8) implies that (fe, o) ref,k++1 (s, a) gives the sum of the estimated reference functions and squared reference functions at the next states for all agents and all visits (s, a, h)) up the end of round k. (frndy, 11 o o 1 a) gives the sum of the estimated advantage functions, value functions, and squared advantage functions at the next states for all agents and all visits to (s, a, h) in stage 1 and up to the end of round k. Here, (1 (1 (ra clears the historical cumulation if A: and 1 belong to different stages.
Next, the central server updates the estimated Q-function for all (s, a, h) triples with stage renewal while keeping others unchanged:
2h min ( 1.122 H > th1 + 1 = = V(s, a, 4).
(10)
Here, Q 2 advantage type update used in /Zhnn et al. (2020), respectively:
represents the Hoeffding-type used in Zheng al. (2024a). and the reference-
2 1+1,1 (8, a) = (n(s,a) + K4
val,b++ /n k+1 + 1/2 1441,1 (8, (8,
(11)
2 (s,a) as) 1/ ref k /N/ +1 + ph
adv,tt /nk /n + bn
k b (s.
(12)
In these updates where stage renewal happens, N N stage thr, respectively. Thus, Ph val.k+1 /n is the stage-wise mean of the estimated value function, 1h .dv,A++1 /n is the stage-wise mean of the estimated advantage function, and 1t; ref, /N gives
n b+1 count all historical visits and visits in
the all-history estimated mean of reference function. b b% k are upper confidence bounds (UCB) that dominate the variances in the above empirical mean estimations. Their expressions are provided in line 15 of Algorithm|]
Next, the central server updates the estimated V-function and the policy as follows:
Ville max Qh (s. s+1 (s)
arg max Qh+t (s,a') (D,),,(ss,))) E S [H]
(13)
d'EA
Step 5. Updates of the reference function. With a constant No E R4,, the central server conducts
y 1 (s) V. < (s)l(kk
kanl + Vol k. ( 2 ko.n]. (s, E E x [M].
h/
(14)
Here, hish inf (k: N+ EvEA N N (s, 2 No). Equation 14 means that at the end of round k; for all (s, h) such that the stage for (s, (s), h) is renewed, we will update the reference function at (s, h) based on the updated value function V if round is the first round such that the global visiting number to (s. /t) across all complete stages reaches No. "First round" indicates that the reference update on each (s, h) happens at most once during the whole learning process with
k 1,2 ., and the reference function on (s. h) will be settled after its update. This design matches the single-agent algorithms in Zhang et al. (2200) and et al. (202T)
Now are ready to provide FedQ-Advantern in Algorithms/ I and a for the behaviors of the central server and the agents. In Algorithm [ To limits the total number of steps for all agents. Line 20 in Algorithm [ Jupdates the reference function at (s. h)) when the visiting number exceeds No for the first time and keeps it unchanged for other situations, coinciding with Equation (14).
3.3 INTUITION BEHIND THE ALGORITHM DESIGN
Exponentially increasing stage sizes: infrequent policy switching. FedQ-Advantage guarantees that (x+1(8,00 a, h) (1 ((1)/ Hy (s. a, h), where (e(s, a, h) represents the number of visits
to (s, a, h) in stage t. The exponential increasing rate is controlled by the threshold cf (s, a) in
Equation 2 and stage renewal condition in Equation (7). By analyzing the two cases of Equation
we can prove that n +1 < (1 + 2/ H Jnf which implies that 3/++1 < (1 + 2/ H/H)). Equation
further implies that yt-1
The details are provided in (d) and (e) of Lemma D.I Our
visits in stages satisfy similar exponential increasing pattern yt+1 = =1(1 1 1/H)yr in Zhang
jet al. (2020), and Adv--Adatt switches policies infrequently since estimated Q Q-QQQQuueeee functions and the policies are only updated after stage renewals.
7

---

Published as a conference paper at ICLR 2025
Algorithm 1 FedQQAdvantage (Central Server)
1: Input and Initialization: To, No E N+. (0, Functions 2, = Vi = Vi = H, func-
tion I
functions I N₁ n/ A phi 1h adv,1
H4 val,1 othcl Oh o
0, V(s, a, ft.. Arbitrary deterministic policy n². Ratep k O. Vayn E (TRUE, FALSE).
2: while Rstep < To do
3: % Step 1. Coordinated exploration for agents.
4: Broadcast ε² and (V,, Vire nř. nij); a(s,a,h) with a (s) ) to all clients.
% Step 2. Event-trigge triggered termination of exploration.
5: if Uayn TRUE then
6: Wait until receiving an abortion signal and send the signal to all agents.
7: else
8:
Wait until receiving abortion signals from all agents.
9:
end if
m.k Receive nn m.k and het Ph, Mi horeet h (()) h) from agents.
mik
10:
Calculate sk+1 (H,, o) pel,k+1 (uedV p1m ",00 o oadryk k+1 via Equations 6 ( and 9 v(s,a,))
11:
% Step 3. Stage renewal. do
12:
for V(,
if +++ (s, 2 (s, () (1 (1+ a), then
13:
(Stage renewal) Il I,,, I, n = = mh = O. N (s, + n+21
14:
% Step 4. Updates of estimated value functions and policies.
Update ( a) based on Equations (1 to 12 Here, Un bk+ 1 (8, = /2H22/mh k+1
15:
Un 2 (8,
2 (a /N
+ 2 par k+1 / /n 10/((L/NN
(4/n k+1 1/3/4113/4444/ + c/Nitt + e/nk
k+11
log(2/p), vark st.
ket /N4
on
(uh (1tt /N/tt)22 vårgev adv hh gdd
/n (uh
addv,+l /mh 12t22
16:
else
(Stage unchanged) Q I Qh Ih p
nt. n n N N 0, n/
k+l
18:
end if
end for
20:
Find V. , - k+1 from Equation 13 1
mpffAt T[ Not1 Nxt1((, (8,a') 2 Vos,
% Step 5. Updates of the reference Function.
Viet be = Vieffh (1 (1-1,, (1-1 (1 p t++ I
(1- In ().
21:
Netep Em.aa. nhh
end while
Algorithm FedQ-Advantage (Agent mn round k)
Receive n and (V/,, Vree, n nt), V(s, a, h) with a = (s) from the central server.
2: Initialization: functions ny PKRte Phaadv Pha T K, < O, ( (s),
3: while no abortion signal sent from the central server do (s, 4: while ni (s, a) < c (s, a), V(s, a, h) with a = (s) do
5: Collect a new trajectory {(8h, Th) T with an x;(s))
6:
Update local incremental quantities: (n Mhaef ah, Phyval h.eeft a an)
mm
7: = (1, V441 yadv,
V [V (1) wh.
8: end while
9: Send an abortion signal to the central server.
10: end while
11: Functions
(no -hhar Ph Mi o hyret> m,k m.k mik mak mik mikk } to the central ) V(s (s), h) and send { (ni peg Pi sat of he o h e.h server.
(n mm.nk m.k mick myk mik mikk pef Ph,adv vat o hefe haad))
Reference-advvantage decompositions: the key to the almost optimal regret. Q Q-leannng algo- rithms (Jin et al. 2018 Bai al. 2019 Zhang et al. 2020 Li al. 2021 Zheng et al. 2024a update
8

---

Published as a conference paper at ICLR 2025
the estimated Q-function in the following form: Qu(s.a) < rn(s,a) EST s,a. v(+1) + b. Here, b > O is the upper confidence bound (UCB) that promotes exploration, and EST(.) represents the empirical estimation, which takes the form a weighted sum of the historically estimated value functions for the next states following the visits to (s, a, h). This update is motivated by the Bellman IP P.sa.. Vh+++ can be decomposed into the variance
optimality equation. The error EST(PP,..tt V from the random transitions to the next states and the bias in the estimated value functions. To handle the bias that is more severe in the early visits, Jiin et al. (2018); Bai et al. (2019); Zheng al. (2024a) required that the weights concentrate on the most recent O (1/H) proportion of visits like Equation ( that only use visits in the current stage, which causes sample inefficiency and suboptimal regret.
To address this issue, Zhang et al. (020); Li et al. (202T). Equation (12 in Step 4 represents the decomposition. We
uses the veference-advantee decomposition adopted by
decompose the estimation of IP s, Vh+1 into the reference part f1). -et,k+1 /N and the advantage part
8% m 1 For the advantage part, we use stage-wise mean to eliminate the large biases in early value estimations. For the reference part, since the reference function will settle after No = (()) visits as shown in Step 5, we can neglect the bias and use the mean of all historical visits. This design reduces the error in the empirical estimation by improving the sample efficiency in the reference decomposition, part and restricting the error ranges in the advantage part. The anference-advantaan together with the exponentially increasing rate of stage sizes, is the key to our improved regret compared to Zheng et al. (2024a) and our linear regret speedup compared to the almost optimal regret given in Zhang et al. (2020).
Heterogeneous event-triggered communication: the key to our improved communication cost. RedQ-Advantee uses of, given in Equation (2) to limit the number of new visits for agent m in round l. While the first case in Equation (2 is similar the homogeneous condition in Zheng et al. 2024a). we design the second case to allow more new visits when the number of existing visits the current stage is small. Specifically, when n 2 MH and nf (1 1/H)n ci | [- Thus, FedQ-Advantage allows more visits in the early rounds of each stage compared to Zheng et al. (2024a) and reduces the number of communication rounds, which is key our improved communication cost shown in Table T
[(ng - (o5--n)//mm /
Optional forced synchronization: accommodating heterogeneous exploration speeds. Section 3.2 and eqs. (4) and (5) highlight the effect of the optional forced synchronization used in Step 2. Section 3.2 shows a common limitation of new visits, which is sufficient for our linear regret speedup compared to the single-agent algorithm in Zhang et al. (2020). Next, we discuss the robustness and trade-offs of optional forced synchronization when under heterogeneous exploration speeds of agents.
When optional forced synchronization enabled (i.c., Ueyn TRUE), exploration and commu- nication occur as soon as one agent reaches the threshold (s,, a). This allows faster agents to avoid waiting for slower ones, minimizing waiting time. However, Equation (4) guarantees sufficient exploration by only one agent, resulting in varied episode counts across agents. This configuration is suitable for tasks sensitive to waiting time.
When optional forced synchronization is disabled (i.e., Usyn = FALSE), communication occurs only after all agents meet the threshold ct (s. a). Equation 5) ensures sufficient exploration by all agents, with episode counts being roughly balanced. This allows for more extensive exploration within round, reducing communication costs but potentially increasing waiting time for faster agents.
4 PERFORMANCE GUARANTEES
Next, we provide regret upper bound for FedQ-Advantage follows.
Theorem 4.1 (Regret of FedQ-Advantage Let log(2/p) with p e (0, 1) and No- = 5184 SAH 16 MSAH with 3 E (0, H]. For Algorithms and with probability at least 1 100--(4555 (4SA7
B
5SAT7/H H 5SAT, + 5)p, we have
(T) Ō ((1
9

---

Published as a conference paper at ICLR 2025
Here, K is the total number of rounds. T= H n is the total number of steps for each agent,
T = (2+ To MSAH (H+1),, and Ô hides logarithmic nultipliers on To, M1, H, A, 1/p and poly represents some polynomial. This result does not depend on the value of Magn. See Equation (26) Appendix for the complete upper bound.
Theorem 4.1 indicates that the total regret scales O(VH?MTSA) when T larger than some polynomal of MHSA and / = (2(1) in No. This is almost optimal compared to the information bound Ω AMT) and is better than Ö(v (VVHSSA AMT) for algorithms in Zheng et al. (024a). When M our regret bound becomes ( 3) HHTSA) when T is large, which is better than Õ((1 + / in Zhang al. (2000) thanks to our tighter regret analysis. This also means that to reach an almost optimal regret bound, Zhang et al. 2020) requires 8 f O(I/VH) and FedQ-Advantage lays a weaker one 3 S (2(1). When M > 1. locusing on the dominate terms Ô ((1 + MSAMTT when T large, our algorithm achieves a near-linear regret speedup while the overhead term O1Mpoly 1/3) results from the burn-in cost for using reference- advantage decomposition (Zhang et al. 2020), and the S (M) visits collected in the first stage for each (s, 0, h), which servers as the multi-agent burn-in cost that common in federated algorithms
(see e.g. Zheng et al. (2024a); Woo et al. (2023 2024)).
Next, we discuss the improved communication cost compared to Zheng et al. (2024a) as follows.
Theorem 4.2 (Communication rounds of Fevanadvantage). Under Algorithms 7 aand 2 with Usyn
TRUE, the number of communication rounds K and the total number of steps T satisly that
T
+1)
K S MSAH 4MSAAH( +3) log
SAH
Uayn FALSE, the number of communication rounds K and the total number of steps T satisfy
K s SAH 4SAHH + +333log log ( T
SAHS +1)
Theorem 4.2
implies if Ueyn = TRUE and T is sufficiently large, K=
SA H) log T).
Since the total number of communicated scalars is O(M HS) in each round, the total communication cost scales in O(M² 3 A(log H) log T). Thanks to the heterogeneous design in ct a), is better than (M S2 A log T') for FedQ-Hoeffding and FedQ-Bernstein in Zheng et al. (2024a). If Uayn = FALSE, when 7' is sufficiently large, K = SAlog H) log which is independent of M. Since the total number of communicated scalars is O(MHS) each round, the total communication cost scales in ( A(loo H) log T).
Our result for Usyn FALSE also implies low policy switching cost, which is defined as the times of policy switching. Knowing that the cost of Zhang al. (2020) is O(H2 log(T)) and K 0 (H2 H) log for FedQ-Advantaaee. our communication round matches the policy switching cost up to a logarithmic factor under restrictions on sharing original trajectories. We also remark Equation (102) in Appendix shows that Aevan-dd can also reach the same local switching cost as Zhang al. (2020). We refer readers to Zhang et al. (2020) for more information.
We will provide the complete proofs of Theorems
and 4.2 in Appendices and respectively.
CONCLUSION
This paper develops the model-free FRL algorithm FedQ-Advantage with provably almost optimal regret and logarithmic communication cost. Specifically, it achieves an almost-optimal regret, reaching the information bound up to a logarithmic factor and near-linear regret speedup compared to its single-agent counterpart when the time horizon sufficiently large. Our algorithm also improves the logarithmic communication cost in the literature. Technically, anference-advantaee decomposition and designs separate mechanisms for synchronization and policy switching, which can find broader applications for other RI. problems.
algorithm uses the UCB,
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENT
The work of Z. Zheng, H. Zhang, and L. Xue was supported by the U.S. National Science Foundation under the grants DMS-1811552, DMS-1953189 and CCF-2007823 and by the U.S. National Institutes of Health under the grant 1R01GM152812.
REFERENCES
Alekh Agarwal, Sham Kakade, and Lin F Yang. Model-based reinforcement learning with a generative model is minimax optimal. In Conference on Learning Theory, pp. 67-83. PMLR, 2020.
Mridul Agarwal, Bhargav Ganguly, and Vaneet Aggarwal. Communication efficient parallel rein- forcement learning. In Uncertainty in Artificial Intelligence, pp. 247-256. PMLR, 2021.
Shipra Agrawal and Randy Jia. Optimistic posterior sampling for reinforcement learning: worst-case regret bounds. Advances in Neural Information Processing Systems, 30, 2017.
Aqeel Anwar and Arijit Raychowdhury. Multi-task federated reinforcement learning with adversaries. arXiv preprint arXiv: 20l.066303. 2021.
Mahmoud Assran, Joshua Romoff, Nicolas Ballas, Joelle Pineau, and Michael Rabbat. Gossip-based actor-learner architectures for deep reinforcement learning. Advances in Neural Information Processing Systems, 32, 2019.
Peter Auer, Thomas Jaksch, and Ronald Ortner. Near-optimal regret bounds for reinforcement learning, Advances in Neural Information Processing Systems, 21, 2008.
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for rein- forcement learning. In International Conference on Machine Learning, pp. 263-272. PMLR, 2017.
Yu Bai, Tengyang Xie, Nan Jiang, and Yu-Xiang Wang. Provably efficient q-learning with low switching cost. Advances Neural Information Processing Systems, 32, 2019.
Soumya Banerjee, Samia Bouzefrane, and Amar Abane. Identity management with hybrid blockchain learning. In 2021 IEEE
approach: A deliberate extension with federated-inverse-reiin 22nd International Conference on High Performance Switching and Routing (HPSR), pp. 1 1-6.
IEEE, 2021.
Ali Beikmohammadi. Sarit Khirirat, and Sindri Magnússon. Compressed federated reinforcement learning with generative model. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp. 20-37. Springer, 2024.
Tianyi Chen, Kaiqing Zhang, Georgios B Giannakis, and Tamer Başar. Communictionn-fficien policy gradient methods for distributed reinforcement learning. IEEE Transactions on Control of Network Systems. 9(2):917-229, 2021a.
Yiding Chen, Xuezhou Zhang, Kaiqing Zhang, Mengdi Wang, and Xiaojin Zhu. Byzantinerrobust online and offline distributed reinforcement learning. In International Conference on Artificial Intelligence and Statistics, pp. 3230-3269. PMLR, 2023.
Ziyi Chen, Zhou, and Rongrong Chen. Multi-agent off-policy tde with near-optimal sample and communication complexity. In 202/ 55th Asilomur Conference on Signals, Systems, and Computers, pp. 504-508. IEEE, 2021b.
Ziyi Chen, Yi Zhou, Rong-Rong Chen, and Shaofeng Zou. Sample and communication-efficieeen decentralized actor-critic algorithms with finite-time analysis. International Conference on Machine Learning, pp. 3794-3834, PMLR, 2022.
Christoph Dann, Lihong Li. Wei Wei. and Emma Brunskill. Policy certificates: Towards accountable reinforcement learning. International Conference on Machine Learning, pp. 1507-1516. PMLR, 2019.
11

---

Published as a conference paper at ICLR 2025
Thinh Doan, Siva Maguluri, and Justin Romberg. Finite-time analysis of distributed td (0) with linear function approximation on multi-agent reinforcement learning. In International Conference on Machine Learning, pp. 1626-1635, PMLR, 2019.
Thinh T Doan, Siva Theja Maguluri, and Justin Romberg. Finite-time performance of distributed temporal-differenn learning with linear function approximation. SIAM Journal on Mathematics of Data Science, 3(1):298-333)) 320, 2021.
Omar Darwiche Domingues, Pierre Ménard, Emilie Kaufmann, and Michal Valko. Episodic rein- forcement learning in finite mdps: Minimax lower bounds revisited. In Algorithmic Learning Theory, pp. 578-598, PMLR, 2021.
Simon S Du, Jianshu Chen, Lihong Li, Lin Xiao, and Dengyong Zhou. Stochastic variance reduction methods for policy evaluation. In International Conference Machine Learning, pp. (049-1058) PMLR, 2017.
Abhimanyu Dubey and Alex Pentland. Provably efficient cooperative multi-agent reinforcement learning with function approximation. arXiv preprint arXiv:2103.04972, 2021.
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, pp- 1407-1416. PMLR, 2018
Flint Xiaofeng Fan. Yining Ma, Zhongxiang Dai, Wei Jing, Cheston Tan, and Bryan Kian Hsiang Low. Fault-tolerant federated reinforcement learning with theoretical guarantee. Advances in Neural Information Processing Systems, 34:1007-1021, 2021.
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, pp. 28 2810-2812, 2023.
Swetha Ganesh, Jiayu Chen, Gugan Thoppe, and Vaneet Aggarwal. Global convergence guarantees for federated policy gradient methods with adversaries. arXiv preprint arXiv:2403.09% 2024.
Zijun Gao, Yanjun Han, Zhimei Ren, and Zhengqing Zhou, Batched multi-armed bandits problem. Advances in Neural Information Processing Systems, 32, 2019.
Wei Gong, Linxiao Cao, Yifei Zhu, Fang Zuo, Xin He, and Haoquan Zhou. Federated inverse reinforcement learning for smart ieus with differential privacy. IEEE Internet of Things Journal, 10021):19117-19124, 2023.
Robert M Gower, Mark Schmidt, Francis Bach, and Peter Richtárik. Variance-reduced methods for machine learning. Proceedings of the IEEE, 108( 1961-19889333 2020.
Zhaohan Guo and Emma Brunskill. Concurrent pac rl. In Proceedings the AAAI Conference on the
Artificial Intelligence, volume 29, pp. 2624-2630, 2015.
Hao-Lun Hsu, Weixin Wang, Miroslav Pajie, and Pan Xu. Randomized exploration in cooperative multi-agent reinforcement learning. arXiv preprint arXiv:2404. 10728, 2024.
Chi Jin, Zeyuan Allen-Zhu Sebastien Bubeck, and Michael Jordan. Is q-learning provably efficient?
Advances in Neural Information Processing Systems, 31, 2018.
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on learning theory, pp. 2137-2143, PMLR, 2020.
Hao Jin, Yang Peng, Wenhao Yang, Shusen Wang, and Zhihua Zhang. Federated reinforcement learning with environment heterogeneity. In International Conference on Artificial Intelligence and Statistics, pp. 18-37. PMLR, 2022.
Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. Advances in Neural Information Processing Systems, 26, 2013.
12

---

Published as a conference paper at ICLR 2025
Sham Kakade, Mengdi Wang, and Lin F Yang. Variance reduction methods for sublinear reinforce- ment learning. arXiv preprint 1021v1182.09114, 2018.
Koulik Khamaru, Ashwin Pananjady, Feng Ruan, Martin Wainwright, and Michael Jordan. Is temporal difference learning optimal? an instance-dependent analysis. SIAM Journal Mathematics of Data Science, 3(4):1013-1040 2021.
Sajad Khodadadian, Pranay Sharma, Gauri Joshi, and Siva Theja Maguluri. Federated reinforcement learning: Linear speedup under markovian sampling. In International Conference on Machine Learning, pp. 10997-11057. PMLR, 2022.
Guangchen Lan, Han Wang, James Anderson, Christopher Brinton, and Vancet Aggarwal. Improved communication efficiency federated natural policy gradient via admm-based gradient updates. arXiv preprint a0. /9807, 2023.
Guangchen Lan, Dong-Jun Han, Abolfazl Hashemi, Vaneet Aggarwal, and Christopher G Brinton. Asynchronous federated reinforcement learning with policy gradient updates: Algorithm design and convergence analysis. arXiv preprint arXiv:2404.08003, 2024.
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-7044 2020.
Gen Li, Laixi Shi, Yuxin Chen, Yuantao Gu, and Yuejie Chi. Breaking the sample complexity barrier to regret-optimal model-free reinforcement learning. Advances in Neural Information Processing Systems, 34:17762-17776, 2021.
Rui Liu and Alex Olshevsky. Distributed td (0) with almost no communication. IEEE Control Systems Letters, 2023.
Shicheng Liu and Minghui Zhu. Distributed inverse constrained reinforcement learning for multi- agent systems. Advances in Neural Information Processing Systems, 35:33444-3344 2022.
Shicheng Liu and Minghui Zhu. Meta inverse constrained reinforcement learning: Convergence
guarantee and generalization analysis. In The Twelfth International Conference Learning Representations, 2023.
Shicheng Liu and Minghui Zhu, Learning multi-agent behaviors from distributed and streaming demonstrations. Advances in Neural Information Processing Systems, 36, 2024.
Shicheng Liu and Minghui Zhu. In-trajectory inverse reinforcement learning: Learn incrementally before an ongoing trajectory terminates. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2025.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication--ffiiinn learning of deep networks from decentralized data. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, volume 54, pp. 1273-1282. PMLR, 2017.
Pierre Ménard, Omar Darwiche Domingues, Xuedong Shang, and Michal Valko. Ucb momentum learning: Correcting the bias without forgetting. In International Conference on Machine Learning, pp. 7609-7618. PMLR, 2021.
Yifei Min, Jiafan He, Tianhao Wang, and Quanquan Gu. Cooperative multi-agent reinforcement learning: Asynchronous communication and linear function approximation. International Conference on Machine Learning, pp. 24785-24811. PMLR, 2023.
Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforcement learning. In International Conference Machine Learning, pp. 1928-19999999 1937. PMLR, 2016.
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, pp. 2613-2621. PMLR, 2017.
13

---

Published as a conference paper at ICLR 2025
Vianney Perchet, Philippe Rigollet, Sylvain Chassang, and Erik Snowberg. Batched bandit problems. The Annals of Statistics, 44(2):660 681, 2016.
Dan Qiao, Ming Yin, Ming Min, and Yu-Xiang Wang. Sample-efficient reinforcement learning with loglog (t) switching cost. In International Conference Machine Learning, pp. 18031-18061. PMLR, 2022.
Han Shen, Kaiqing Zhang, Mingyi Hong, and Tianyi Chen. Towards understanding asynchronous advantage actor-critic: Convergence and linear speedup. IEEE Transactions Signal Processing. 2023.
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, pp. 19967-20025. PMLR, 2022.
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 Neural Information Processing Systems, 31, 2018.
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-442, 2023.
Jun Sun, Gang Wang, Georgios B Giannakis, Qinmin Yang, and Zaiyue Yang. Finite-time analysis of decentralized lemporal-diffrennce learning with linear function approximation. In International Conference on Artificial Intelligence and Statistics, pp. 4485-4495. PMLR, 2020.
Sutton and A Barto. Reinforcement Learning: An Introduction. MIT Press, 2018.
Hoi-To Wai. On the convergence of consensus algorithms with markovian noise and gradient bias. In 2020 59th IEEE Conference on Decision and Control (CDC), pp. 4897-4902. IEEE, 2020.
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.
Martin J Wainwright. 1906::9906.04000 04000,04697.220 2019.
Variance-reduced q-learning is minimax optimal. arXiv preprint
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.
Tianhao Wang, Dongruo Zhou, and Quanquan Gu. Provably efficient reinforcement learning with linear function approximation under adaptivity constraints. Advances in Neural Information Processing Systems, 34: 14:13424-13536, 2021.
C. J.J.C. C. Watkins. Learning from Delayed Rewards. PhD thesis, King's College, Oxford, 1989.
Jiin Woo, Gauri Joshi, and Yuejie Chi. The blessing of heterogeneity in federated q- q-learning: Linear speedup and beyond. In International Conference on Machine Learning, pp. 37157-37216, 2023.
Jin Woo, Laixi Shi, Gauri Joshi, and Yuejie Chi. Federated offline reinforcement learning: Col- laborative single-policy coverage suffices. International Conference on Machine Learning, 2024.
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.
Tengyu Xu, Zhe Wang, Yi Zhou, and Yingbin Liang. Reanalysis of variance reduced temporal difference learning. arXiv preprint arXiv:2001.0189, 2020.
Yuling Yan, Gen Li. Yuxin Chen, and Jianqing Fan. The efficacy of pessimism in asynchronous q-learning. IEEE Transactions Information Theory, 2023.
14

---

Published as a conference paper at ICLR 2025
Kunhe Yang. Lin Yang, and Simon Du Q-learning with logarithmic regret. In International Conference on Artificial Intelligence and Statistics, pp. 1576-1584 PMLR, 2021.
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.0020) 2023.
Ming Yin, Yu Bai, and Yu-Xiang Wang. Near-optimal offline reinforcement learning via double variance reduction. Advances in Neural Information Processing Systems, 34:7677-7688, 2021.
Andrea Zanette and Emma Brunskill. Tighter problem-dependent regret bounds in reinforcement learning without domain knowledge using value function bounds. In International Conference on Machine Learning, pp. 7304-7312. PMLR, 2019.
Sihan Zeng. Thinh T Doan, and Justin Romberg. Finite-time analysis of decentralized stochastic approximation with applications in multi-agent and multi-task learning. In 2021 60th IEEE Conference on Decision and Control (CDC), pp. 2641-2646. IEEE, 2021.
Chenyu Zhang, Han Wang, Aritra Mitra, and James Anderson. Finite-time analysis of on-policy heterogeneous federated reinforcement learning. arXiv preprint arXiv:2401.15273 2024.
Haochen Zhang, Zhong Zheng, and Lingzhou Xue. Gap-dependent bounds for federated q-learning. arXiv preprint ar arXiv:2502.02855: 2025.
Zihan Zhang, Yuan Zhou, and Xiangyang Ji. Almost optimal model-free reinforcement learning via reference-advanttage decomposition. Advances in Neural Information Processing Systems, 33: 15198-15207, 2020.
Zihan Zhang, Xiangyang Ji, and Simon Du Is reinforcement learning more difficult than bandits? a near-optimal algorithm escaping the curse of horizon. In Conference on Learning Theory, pp. 4528-4531 PMLR, 2021.
Zihan Zhang, Yuhang Jiang, Yuan Zhou, and Xiangyang Ji. Near-optimal regret bounds for multi- batch reinforcement learning. Advances in Neural Information Processing Systems, 35:24586- 24596, 2022.
Zihan Zhang. Yuxin Chen, Jason Lee, and Simon Du Settling the sample complexity of online reinforcement learning. arXiv preprint arXiv:2307. 13586, 2023.
Fangyuan Zhao, Xuebin Ren, Shusen Yang. Peng Zhao, Rui Zhang, and Xinxin Xu. Federated multi-objective reinforcement learning. Information Sciences, 624:811-832, 2023.
Zhong Zheng, Fengyu Gao, Lingzhou Xue, and Jing Yang. Federated q-learnin:: Linear regret speedup with low communication cost. In The Twelfth International Conference Learning Representations, 2024a.
Zhong Zheng, Haochen Zhang, and Lingzhou Xue. Gap-dependent bounds for q-learning using reference-advantee decomposition. arXiv preprint arXiv:2410.07574, 2024b.
Runlong Zhou, Zhang Zihan, and Simon Shaolei Du Sharp variance-dependent bounds in reinforce- ment learning: Best of both worlds in stochastic and deterministic environments. In International Conference on Machine Learning, pp. 42878-428 42914. PMLR, 2023.
15

---

Published as a conference paper at ICLR 2025
Organization of the appendix. In the appendix, first provide two tables summarize the notations in Section A| Section [ provides related works. Section presents numerical results. Section D provides basic facts of FedQ-Advantage and lemma of concentration inequalities for regret analysis. Section F presents the proof of Theorem 4.1 (regret). Section presents the proof of
Theorem 4.2 (communication cost).
A NOTATION TABLES
In this section, we provide two notation tables to enhance the readability of the paper. The notations are categorized into two groups: one group consists of global variables utilized for central server aggregation, while the other group consists of local variables employed for agent training. First,
Table 2: Global Variables
Variable
Definition
VØ"
the state value function at step h under policy π
QR
the state-action value function at step under policy π
V
the state value function at step under the optimal policy π
Q7
the state-action value function at step under the optimal policy "'
P. P
E, P (f (f(+)1) 8h = 8, a)
f(s)
the reference function at step h
Vadv
the advantage function at step h
Vk
the estimated state value function of step / at the beginning of the round k:
the estimated state-action value function of step at the beginning of the round the reference function of step h the beginning of the round l:
Vadv,
the advantage function of step h at the beginning of the round k
(s)
the stage index of the triple (8, a, ht) in the round
I > 1x 11 stage renewal indicator in the round i:
(s,
the total number of visits to (s, a. h) before the stage 1 (s)
(s,a)
the total number of visits to (s, o, h) in the stage (*(
(s)
the number of visits to (s, a, h)) in the stage t (s. a) before the start of round &
n (s)
the number of visits to (s, a, h) the stage t (s, a) before the start round
1h (s,a)
pet.k
the sum of the reference function step h + with regard to all visits to (s, h) before round k
oh (s,a)
ke,k
the sum of the squared reference function at step h + with regard all visits (s, a, h) before round k
the sum of the advantage function at step h + 1 with regard to all visits to (s, a, h)
Ph (s)
during stage 1 and before round k:
ady
(s)
the sum of the squared advantage function step + 1 with regard all visits to (s, a, h) during stage t and before round
P/ (s.a)
val.k k
the sum of the estimated state value function at step / + 1 with regard to all visits
to (s, a, h) during stage f/=1 and before round A
cf (s. a)
the exploration termination constant for triple (s, a, h) reference function renewal indicator in the round k
we introduce some local quantities. For f + letting aa.
(f) E f(s f(skm)))x
(((sa))): a)..m. (s,a) a)) the summation of on the states for all the visits to (s, a, h) in round
16

---

Published as a conference paper at ICLR 2025
Table 3: Local Variables
Variable
Definition
m.kk (s,0) a)
the total number of visits to (s, a, h) of the agent m in the round l:
the sum of the reference function step + with regard to all visits (s, a, of the agent in the round k
(s, (s, a)
(hrer((,, a)
m.k
the sum of the squared reference function at step h + with regard to all visits to
(s, a, h) of the agent m in the round k
Phi (s,
m.k
the sum of the advantage function at step h + 1 with regard to all visits to (s, a, h)
of the agent m in the round k
hh (s,
m.kk
the sum of the squared advantage function step + 1 with regard all visits to (s, a, h) of the agent m in the round k
the sum of the estimated state value function at step h + 1 with regard to all visits to (s, a, h) of the agent m in the round ls
Ph (s, a)
for agent m. When there is no ambiguity, we will use the simplified notation A, (,, ) = A Mms,,, (f).
Then, we let ni (s, a) = (1), 14 (s, a) A (441), Hh (s, a) A (Vaitv.)) m.k
(s, A (V/+1) [,.rer(s, a) A ([VTff(1)) and m.k h, a) 4 ([V
For these functions of (s, a), ni is the local count of visits for agent m in round k. and the remaining ones are local summations related to the reference function, the estimated advantage functions, and the estimated value functions for visits.
Accordingly, we define some global quantities. First, we focus on visiting counts. We let (s, a) Ew <tt, Em nh mit be the total number of visits to (s, a, hi) up to but not includ- ing stage the (x, = -EN'gg' -t Em
n m,k'' be the number of visits to (s,a, h) in the stage
1h Here, n 0 if 1h = 1. We also let (s, -M Em nh mi,k and n (8,a) Ex chith' = Em n
m.kk' be the number of visits to (s, a, h) in the stage 1h or 1k-1 before the ref.k (s, Ew'H' Em Whin 0h gudri (s, a)
start of round k. Next, we provide quantities of summations. Let ph
of (s,
Ev'ee Em mi,k'
Ph .
EM Em Mhiatr
En Em m.,k' o regard to all visits of (s, a, h) before round k, and 14, alv.k ohh udvi 14 function, squared advantage function, and the estimated value function at step h + with regard to visits of (s,a, a,, h) during stage - and before round k.
h,adv and 2h
val.k (s.l(s Ew Em 1h.vall Here, Ph ref and
ref,k represent the sum of the reference function or squared reference function at step h + 1 with
p4lall are the sum of the advantage
B RELATED WORKS
Single-agent episodic MDPs. There are mainly two types of algorithms for reinforcement learning: model-based and model-free learning. Model-based algorithms learn a model from past experience and make decisions based 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 to model-based algorithms. However, model-based algorithms may achieve better learning performance by leveraging the learned model.
Next, we discuss the literature model-basee and model- frreelleeeeeeee algorithms for single- agentt episodic MDPs, Auer et al. (2008). A Agrawal & Jial (2017). Azar et al. (2017), Kakade et al. (2018), Agarwal al. 2020). Dann et al. (2019), Zanette & Brunskill (2019) ZZang et al. (2021 /Zoou et al. (2023)
Zhang et al. 2023) worked on model-based algorithms. Notably, Zhang et al. (2023) provided an algorithm that achieves regret of Ô MSi(//SAl*T) TT, T3) which matches the information lower
bound, Jin al. (2018) Yang et al. (2021) Zhang et al. (2020) Li et al. (2021) and Ménard et al.
17

---

Published as a conference paper at ICLR 2025
(0021 work model-free algorithms. The latter three have introduced algorithms that achieve minimax regret of Ô (VSAH!T).
Variance reduction in RL. The reference-advantage decomposition used in Zhang et al. (2020)
and et al. (2021) is a technique of variance reduction that was originally proposed for fimite- sum
stochastic optimization (see e.g. Gower et al. 20 Johnson & Zhang 2013);BB [Nguyen et al. (2017))
Later on, model-free RL algorithms also used variance reduction to improve the sample effciencyy
For example, it was used in learning with generative models (Sidford et al. 2018 2023 Wainwright
2019), policy evaluation (Du et al. [017]] Khamaru et al. [201 Wai ai et al. 2019: Xu et al. (0220)
offline RL (Shi et al. 2022; Yin et al. 2021). ). and Q-learning (Li et al. 2020 Zhang et al. 2020 al.
202T Yan al. 2023).
RL with low switching cost and batched RI. Research in RL with low-switching cost aims to minimize the number of policy switches while maintaining comparable regret bounds to fully adaptive counterparts, and it can be applied to federated RL. In batched RL (e.g.. (e.g..Perrchet Perrceet et al. (2016). Gao
al. 2219)), 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. [Bai et al. (2019)
first introduced the problem of RL with low-switching cost and proposed a Q-learning algorithm
with lazy updates, achieving Ó(S ((SAF' log T) switching costs. This work was advanced by Zhang et al. (202), which improved the regret upper bound and the switching cost. Additionally, Wang
ct al.
2021 studied RL under the adaptivity constraint. Recently, Qiao et al. (2022) proposed a model-based algorithm with Ölog log T') switching costs. Zhang et al. (2022) proposed a batched RL algorithm that is well-suited for the federated setting. Both /Zheng al. (2024b) and Zhang et al.
(2025) analyzed low switching cost in the gap-dependent setting.
Multi-agent RL (MARL) with event- communications. We review a few recent works for on-policy MARL with linear function approximations. Dubey & Pentland| (202T) introduced Coop- LSVI for cooperative MARL. Min et al. (2023) proposed an asynchronous version of LSVI-UCB that originates from Jin et al. (2020), matching the same regret bound with improved communication complexity compared to Dubey & Pentland (202I). Hsu et al. (2024) developed two algorithms
that incorporate randomized exploration, achieving the same regret and communication complexity as Min et al. (2023). Dubey & Pentland (202T); ; Min al. (2023); Hsu et al. (2024) employed event-triggered communication conditions based on determinants of certain quantities. Different from our federated algorithm, during the synchronization in Dubey & Pentland (202T) and Min et al.
(2023), 3 local agents share original rewards or trajectories with the server. On the other hand, Hsu let al. 2024) reduces communication cost by sharing compressed statistics 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. Gurithhs,,GGu&&& & Brunskil] (2015), [Zheg et al. (2024a).
and Woo et al.] (2023) focused on linear speed up. Agarwal et al. (2021) proposed a parallel RL algorithm with low communication cost. |Woo al. (023) ) and Woo et al.) (2024) discussed the improved covering power of heterogeneity. Wu et al. (202T) and [hen et al. (2023) worked
on robustness. Particularly, Chen al. (2023) proposed algorithms in both offline and online settings, obtaining near oottiml sample complexities and achieving superior robustness guarantees. In addition, several works have investigated value-based algorithms such as Q-learning in different settings, including [Beikmohamman et al. (2024), Jin et al. (2022). (2022)_KKooae Khodadadian et al. (2022), Fan al. (2023), Woo et al. (2023). and Woo al. (2024); Anwar Raychowdhury (2021) y Zhao et al.
(2023) : Yang et al. (2023) ; Zhang et al. (2024). The convergence of decentralized temporal difference algorithms has been analyzed by Doan et al. (2019). Doan al. (202T), Chen et al. (2021b) Sun et al.)
(2020). Wail (2020), Wang et al. 2220)) Zeng et al. (2021), and Liu & Olshevsky (2023).
policy gradient algorithms have been studied by [Chnn et al. (2021a) and |Fan et al.) (2021). Lan et al. (2023) 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 Ganesh et al. (2024). Lan et al. (2024) proposes an algorithm to address the challenge of lagged policies in asynchronous settings.
Some other works focus on policy gradient- algorithms. Communication-effiiin
The convergence of distributed actor-critic algorithms has been analyzed by Shen et al. (023) and
Chen et al. (2022). Federated actor-learner architectures have been explored by Assran al. 2019)
18

---

Published as a conference paper at ICLR 2025
Espeholt et al. (2018) and Mnih et al. (2016). Distributed inverse reinforcement learning has been
examined by Banerjee et al. (2021): ): Gong et al. (2023): Liu & Zhu 2022 2023 2024 2025).
C NUMERICAL EXPERIMENTS
C.I EXPERIMENTS COMPARING CANDIDATE ALGORITHMS
In this subsection, we conduct experiments in a synthetic environment to demonstrate the better regret and communication cost of FedO-Advantage compared to TedQQ-Hoeffüing and FedQ-Bernstein proposed by (Zheng et al. 2024a). We follow Zheng et al. (2024a) to use forced synchronization and generate synthetic environment to evaluate the proposed algorithms on tabular episodic MDP. We set H = 10, S = 5, and A = 5. The reward (s, a) for each (s, a, h) is generated independently and uniformly random from [0, 1J. PP(.- 8, a) is generated on the S-dimensional simplex independently and uniformly at random for (s, a, h). Under the given MDP, we set M = 10 and generate 10s episodes for each agent, resulting in a total of 10 episodes for all algorithms. For each episode, we randomly choose the initial state uniformly from the S states. In FedQ- Hoeefdinn and FedO-Bernstein, we use their nyper-paramese
settings based on their publicly available code For Fed(Q-Advantage, we set = 1 and No 200. To show error bars, we collect 10 sample paths for all algorithms under the same MDP environment and show the regret and communication cost in Figure 2 For both panels, the solid line represents the median of the 10 sample paths, while the shaded area shows the 10th and 90th percentiles.
PsdO Hoeflcing Bomascin Advanbage
120
102
Hoeffding
80-
Advantage
Bourda Communtann
30000
G0-
20000
10003
40020
Total number eppoodee ACTM
105
Figure 2: Numerical comparison of regrets and communication costs.
The left panel of Figure 2 plots Regret(T)/ /MT versus MT/H, the total number of episodes for all agents, showing the lower regret of FedQ-Advantage compared to FedQ-Hoeffdiig and FedQ- Bernstein. The right panel tracks the number of communication rounds throughout the learning process. All three federated algorithms show a sublinear pattern when I is large, and FedQ-Advantage requires the fewest communication rounds. Since the communication cost for one synchronization is O(M))) for each of the three algorithms, FedQ-Advantan cost. These numerical results are consistent with our theoretical results in Table We also provide numerical experiments to replicate the setting in ZZeng et al. (2024a), show the performance on different combinations of H, S, A, and explore the multi-agent speedup in Appendix C.3] The conclusions are consistent with those for Figure
enjoys the least communication
C.2 EXPERIMENTS FOR MULTI-AGENT SPEEDUP.
In this subsection, we provide experiments on the multi-agent speedup of FedQ-Advantage under the same experimental setting Appendix C.I Figure 3 reports R(T)/ /T versus T/H based on the 10 sample trajectories for FedQ-Ad Advantag and UCB-A. Here, R(T) = Regret(T)/M. UCB-A is our
All the experiments limited a single core and 4GB RAM. The total execution time is less than 2 hours. The code for the numerical experiments is included in the supplementary materials along with the submission.
with Intel Xeon E5 E5-2650v4 (2.2GHz) and 100 cores. Each replication
https: / http:://ppeeeevieeeeeee ew, net/attachment wew.fffceeeeaanaeeeeeee....
ementary.
material
19

---

Published as a conference paper at ICLR 2025
single-agent counterpart from Zhang et al. 2020)) and show the experimental results for both 10 episodes for the single-agent experiment and 10 episodes, representing the situation where a single agent generates all episodes for Fednt-dvantage under high communication cost. When showing R(T)) for UCB-A with 10 episodes, we pretend that M = 10 and the total number of episodes is comparable. We find that Fedn-Advantage shows multi-agent speedup compared to UCB-A with 10 episodes. However, it exhibits larger regret compared to UCB-A with 10t episodes, which results from the multi-agent burn-in cost discussed in Section 4
10 that the three situations
16
14
UCB-A: 10
12
10 FedQ Advantad
10
RONTT
6
20000
40000
60000
80000
100000
T/H
Figure 3: Multi-agent speedup
C.3 OTHER COMBINATIONS OF H,
Figure 3 gives additional numerical experiment under different combinations of A. The top
panels show 10 replications on S 3, A 2, H = 5, which replicates the experiments in Zheng et al. 2024a). The second one chooses relatively large parameters where H 20, 20, A and shows one replication. The conclusion is the same as that in Appendix C.I
D BASIC FACTS AND CONCENTRATION INEQUALITIES
In this section, we provide some basic facts and lemmas of concentration inequalities for FedQ- Advantage. For any triple (s, a, h)) S x A [H], we let (s, a) Em.k.ek ni "1,'AI[t < t)
be
the number of visits to (s, a, h) up to and including stage / and v (8, a) Em n "T. !
be the visiting number stage t. Here, we have that Y = y = 0, No. = y . y -h We also denote Tí, (s, a) = 1 (s, a) as the total number of stages for (s, a, h). Here, we emphasize that the stage renewal condition might not be triggered in
for the last stage T, (s. a).
Next, we assign an order to the visits of any (s, a, h). Let (, a, h)) denote the i-th visit to (s, a, h) in RedQ-Advantage for E N4. and (k1, (s, a, h), mL, (s, h), ju, (s, a, h)) be the corresponding (round, agent, episode) index of the i-th visit. Similarly, let (s, a, h, k), E [n (s, a)] denote the i-th visit to (s, a, h) during the stage (s. - 1, and (Ar, (s, a, h, k), m. (s, a, h, k). Ju, (s, a, h. k)) be the corresponding (round, agent, episode) index of the i-th visit (s h, k)) The indices follow the chronological order of the visits. Specifically, under the synchronization assumption n m, n Vm E [M] ]. viable order be determined by the "round index first, episode index second, agent
20

---

Published as a conference paper at ICLR 2025
1750
1500
1250
RegreitX SH
1000
x
230
300
2-
230
Ted -loettonn
red0 Germinan
Nu00 Advartage
50000
100000
250000
300000
5000
10000
15000
20000
23000
30020
Total
(a) Regret: replication
(b) Communication cost: replication
leb
-icefliing
1750
1500
Bounds of Communcatioo
Fedt-lliettding
1000
Fed Bedt-Beembenn
Aedi--cventngge
500-
250
Tobal sumber aphiades AFTMV
366
165
(c) Regret: large scale
(d) Communication cost: large scale
Figure 4: Additional Experiments.
The upper panels (a) and (b) replicate the numerical setting
in Zheng al. (2024a) where 5 A 2, H 5. The bottom panels (c) and (d) perform experiments with H 20, S = 2
index third" rule. When hs is clear from the context, we use Li, li, (k, m, J) (ki, m. m.j),, for simplicity.
Next, we provide Lemma D.I on some basic relationships for quantities in FedQ-Advantage Lemma D.1. For any (s,a, S Ax [H] [K]. the following relationships hold for FedO-Advantage.
(a) To T.
m.k (b) n (s, a) S (s, Vm E [M]. In addition, Vk E [K], there exists (s, a, h, m)
S Ax [H] [M] such that ny mik (s, (s)
(c) Tf (8, a) 2, we have MH & Y (s) < MH M
(d) If (s,
> 0, we have that n k++ (s, < (1 + 2/ Hm wk E [K].
(x.))
vy (s.a)
(e) 1 1/2 I
11 [1, 2], t N. In addition, (s.a)
5
3n (0.0)
+
2
H
0 1 < y (s.a) (x(aa)
<2
(T(s,a) 1].
(g) The following relationships hold.
() a) yf (8, a) < 2H,, Vt E (T, - -1].
(15)
21

---

Published as a conference paper at ICLR 2025
( (VVi(s,a) - ve (T) - (16)
H
2 (),
[H, (s,
(17)
(h) Esahh Uh
Til(s,a-1 (s,a) & (H+) LT Eea Sh.
Tu(saa) (9M)))9M)
1To + H
(i) Denote (2+ H To + MSAH(H + 1), we have
T S (2+ (2+ t + MSAH(H + +1.
H
( (s.a) < (h(s.)) V A [K- 1I.
++ (s) S (s). ( (s) S S. (s) v(s.,,,,,))
Here, use Ex,a simplified notation for ExEs EoEA and Exa,h as a simplified notation for Eoes EaEA k= Th is the simplified notation of (T'T,ss, a). Those simplifications will also be used later.
Proof of Lemma D.1
(a) This relationship holds from the stopping condition of the loop (line
2) in Algorithm
(b) From the triggering condition for terminating the exploration in round (line in Algorithm we can prove the relationship.
(c) Since (s, a) 2 2, there exists a round satisfying (h, a) 1 and + (s, a)
Then according to Equation 77). we have ()) = hit+1 (s, a) 2 MH. Meanwhile, according to (b), we have:
( a) (s, (s) Σ
m.k (s, a) n
S (n a) + (c S (x) M.
Since round l: is in stage 1, we know stage 1 is not renewed before the start of round Then according to Equation 7 and the definition of n (s, a), we have n (s, a) I MH and Y (s, a) < (x) + M MH + M.
(d) According to Equation and the definition of n a), we have
()) S
Iro S (s, S ( # m a). then according to Equation 2 we have:
n (n((s,a) - (8, +1)
a a) $ a a) + Mc s (s a) + M
M
n a) M.
Since (f, a) > 0, we know (s) > 1 and then n (s) 2 (s, 2 MH. There-
fore, nt, k+1 ( < ( M (1+
(1 1/ (y < (1. <1= a). then according to Equation 2
have:
n hit s
(s,a) in a) + (s, & (s. + M. MH n a) $ (1+ / In((s,a).
Therefore, n/ a) s (1 (s,
22

---

Published as a conference paper at ICLR 2025
(e) Fort S as, 22, there exists round & satisfying (s, a) ++1 and +++ t (s.a) =
Then according to Equation 7 we have yn v (s,a) = f (s, a) 2 (1 (1+1/H)n](s.a))
(1 + H/H)/h (s, a). Moreover, according to (d), we have y/ (s, n/2 (8,0) S
(1 + 2/H4),
(s, a) = (1 2/) (s,
For / = (s, - 1, we have Uh (8,a) = nh (s, 2 (8, =
2/ 2/H1)// (s,
(f) According to (c), for t $ [h a) we
we have yh (5, a) S (1 (1+2/H)jb (s. a). Then:
1 Y (s.0) a) (s,0a)
= =1+ yh (s, S1+ (1+ 2 Juh (3,0)
2 < 4.
2 +
as)
(s,
(s,
H
(g) We will use the mathematical induction to prove the Equation 15
Fort=1
(s, 1 1 211
(8,
If Y (a.aa
Vi (ss,a) S 2H, then for t (2 t a) 1). according to (e), we have yf (s, 2
(1 + 1/H)ynh 1-1 (o,0-sss,,, a). Then:
(s.a).
(s(s,a) =1+
V (s,a) ()
(s, I1+
2H
11
S 2H.
(s,a)
(1+ # 1h
(s,aa
1 H
Therefore, we finish the proof of the Equation 15
For Equation
16
we have:
3V (v (VY%(s,0) y (s,a)
(V (3,0))
(i
Vvi(s, (a(s,a)-300 3/H
()
ai
-V a).aa)-3 3VH
(x.e)
(=.a) 1y (s.a)
Mr, (s,a)
2 (s, a). 3VH
V2H + /2H -1 (3)
The second last inequality is because (s.a) (,,a)
s 2H according to Equation 15
For Equation 11 according to (e), we have (8, a) S (1+ + 21+2/H)**
y/ (s, a) for any
h E [H). Then:
(s. Em h-t++ (s,
HH + 3y
(s,a) ()
(3,a)
H (1
2 )
2
+
H (1 (1 +
2
H
Because (1+ ))"² is increasing in H. we have (1 Therefore,
21 2 3 and 1 - (1+ H
)
3
11
(s, (s,
H 2 (1 )
2 - H
2 +1+
(1+
2
H
H
4
We finish the proof of (g).
(h)
Σ 8.a.h
Ta ((.,,)-1((,0))
Σ
(1 < H +1]
Mh
8,0,h
Σ yh - (s,a))(((([ > #+
s.a.h
23

---

Published as a conference paper at ICLR 2025
Because of (e), we have:
yh Th-
(1 T y (alss,)1/T(sss4) < H +1]
H
(1+ "MMH+ + M).
The last inequality is because v (s,a) (s, v MH + M according (c). Moreover, according to Equation (17). we have
4To Σ TT. 1 (s. [T, 2 H +
Σ (s, (T) H+1| 8,a,k
H h
H
8,0,
The last inequality holds because Therefore, we have
Ex,,h Y - (s, a) S To according to the algorithm.
Σ
yh (h(s,a) (8, (s,
Ea+ H
4T (MH M) +
4To s 9MSAH( +
H
H
s,a,b
8,a,h
Similarly, we have:
Σ s.a.h
(a(a,)) (s,a)
yn
Σ
Uh
Th (s, <
Σ
+
s,a,h
8,0.h
$ (1 +
2 (1) H
Σ
H
4 vn
yT- (s,o][]00)))) 2 #+1
2,0
(M + +1) 4To
H
(i) First, according to (f), we have:
2 2 )r,
(s, []
- >
2 $ H
(s,a)) MH + M.
The last inequality is because of (c). Then we have:
2 Σ (2+
T Σ Y (s, <
y Tn - MH M)
H
s,a,
8,a.h
2 H
(2 +
To + MSAH(H + 1).
The last inequality is because of E.,, h Y -I (1, (s,a) s To according to the algorithm. Because To < T from (a), have:
TST S (2+
+
H I MSAH(H +
(i) According to Equation 10). we know (s, a) is non-increasing with respect to k. Then based on the update rule Equation (13) for V a) and the update rule Equation 114 for pref. (s, (s,a), we find that they also non-increasing with respect to k.
Next, we provide Lemma D.2 that discusses the weighted sum of all the steps.
24

---

Published as a conference paper at ICLR 2025
Lemma D.2. For any non-negative weight sequence {wn(s, d)) and any (0, 1), it holds that
H
wh wh(sh R. k. k.m.j. J.. 11 (/)
ap
m.mm >
1 s
4 Σ
wh(s, (s,
h=1 k.m.
(sh
an
8,0,4
and
w k.mw
an ahim k.m.J k.m.J.y ya
(8
E
I kmm 11
Σ
wn (()s,,)) (s,a)= (s,,))
1=1kmm.
an
s,a.k
For a 1, it holds that
wh (s) k.m.
an ahtmm k.m.d A.moit )
II "
> [ s Σ
wn(ss, an log(H" (s,
No (8 (sth Oh
Am J.mmj
and
wh J.m. On )
Σ
[
m.m.
1] S8H Σ
as ao) (s,a)).
ni (is On ko
s,a,h
Here, J.m.J.
the (s)
(. 0% k.m.)).
Proof of Lemma D.2 According to Equation k.m.j 1, In
15 b, for any (5% kmm A.m. ,1) E S x Ax [M] and
N (s k.m. .h m. k.m.
Pth
k.ms -1
(s komm aa alimm.)
< 2H.
ni (5), an k.mm))
kk.ma -1 kimm a, k.m.)
yb
Therefore, we only need to prove the first and the third inequalities.
We first provide two conclusions. For S and
1, it holds:
1-a
2 (1 - a) 1)z a 2 4 (1 az 1)
(18)
log (x) 2 - 1 x x-1
(19)
Next, we back to the proof. For any (s.a.h) E S x A x [H] and 2 S t (x(s, let
(s.a)
I (e.o) According to (f) Lemma D.1 we have
S x s 4. Using Equation (18) and
Equation 19 it holds:
(8
(((s,a)-aa yx- 2-a 2 4- a) yd (s,
(20)
and
(s, a)) log(Y;"''s,a) 2 (s,
(21)
4y - (s,
25

---

Published as a conference paper at ICLR 2025
Now,
wh (s kima ; -ap )
1
bb > 1
k.m.
No (oh
k.m. Miimatde ja .hh
1= k.mn.
H
wn(sh mim ohh obimm))
miss > 1/
[ k.ms a a k.m. = (s, (s,
(5 tima
k.maaaa" .ah
wa(s,a) - (s, 1| (i ah dl = (s)
E E s.a. m.
()
Σ E
an
I [sstimss an m. = (s)
Σ I (1) =t]
=t]
s,a, k.m.j
a)(s,a)
E1((s) or (.imdd a), (s) =
(s,
s.a.A
kym.
In the last equality, I[(5 t. aa m. (s, (s. 1 if and only if (s miim k.
az
(s, a) and k in stage t of (s, a, a,,,), so mm. 11(0% k.m.d an mm)m (s, () (s,a) a) = t] 1/, (s, a). In
this case, N (s, Y (s, a) and then we have:
H
wh(s k.m.J k.m)j)
The wn(s, (s,))
I k.m. >
1| =
(22)
1= J. (s) m.m. k.m.doo
s,a, t=
Summing Equation 20 for 2 SSSTTA Th(s for any < a < 1, we have:
Tg
a))
4 Ta
a Yh (s, (s, 1-a) S
4
Ta (s, (s)
(23)
(s)
2=
Combining Equation
(2 and Equation
we can finish the proof of the first inequality.
In Equation
22 let 1, we have:
wh(sh (ohiiin an k.m...) k.m.t
Th
y (s,
II
k.m.J 1] Σ kaa
wh(s, a)
Σ
(24)
(5 Sh k.
Y (s)
1=1 k.m.j
Summing Equation
21 for 2 St a)) we have:
Ta
(s
TA
(log(Y((ssaa) log(Y""""ss,,) < log((Y (s,
(25)
2=2 (s,
Combining Equation finish the proof.
24 with Equation
25 finish the proof of the third inequality. Then
Next, we provide auxiliary lemmas.
Lemma D.3. (Azuma-Hoffiding Hoeffding Inequality) Suppose { is a martingale and [X - Xx-1l S C₁. Vk E N almost surely. Then for any positive integers N and any positive real number e, it holds that:
IP (IXN- Xol 2 E) 2exp
2
k= C
Lemma D.4. (Lemma 10 of Zhang et al. 2020
Let {Ma 1o0 be martingale such that
Mo 0 and [M, Mn-1 F = F MI, 1). Then any positive integer n and any e, > 0, we have that:
C. Let V Yarn
Σn Ci B[(M
MR-1)2 where
P [M 2 2/ Var, 2ar,, log(1/p) + +2 clog(1/p)) 2clog(1/p)) < (2nd²/e (c+2)
26

---

Published as a conference paper at ICLR 2025
At the end of this section, we provide a lemma of concentration inequalities.
Lemma D.5. Let = 1og(2/p) with E (0, Using V(s. a. h, k) as the simplified notation for V(s, a, h k) E S A x [M] x [K]. For any function J : S - I. we denote V Vs,an()) P. F (I k.) Next, we define the following events.
m
(mmm)))) - Pasa. Vitta)
2H² nb
1
V (#/+1
S
V(s h,)
i=1
N Vaa vithiiig jet + Vi
2
E2 =
Ixal S
+ He ((s,a,,
NR
Ti
in which X1 is the abbreviation for
N
protkee
(1 (8,,,,h,k)
(8, a)
P Psaan
commiiie #h-1
h+1
N Pssau (lmmslee
Eg-
H (N)
9441
N
Es =
Psya. 1l ummmilles)
(1
I (2,
Sn+1
n V (V
2 1x2l S
Vl
Es-
h+1
)e +
2Hz v(s.a,1,)))
n
Ti
in which X2 is the abbreviation.or for
nit Σ 1% i=1
Paaah - 1 coom.sie ) (v/t1 Vi
X2(3, a, 11,
9h11
Eg
Pa.ah (u.m.0))) ) (Vitt1
Vn#1
)
I <2H 2n
6x11
E
Ps.ah - 1 (emmalle (V/ti1 - vitti )2 9x+1
< 2H² 2n (s. a)e, a(s,
1=1
Eg-
P simis N.mis .a
Il (mmms)
) N (of (ommddd S /2T22
11 k.m.jj
Here, = =
(s) < Nol with (/(())
EaEs N/ a). Especially, Nir (s) 0. Exm
is the abbreviation of Ex= k=
EM EØ We will also use the abbreviation later.
m
11
Σ
2 11 7
1
(P (P.ems Somms,ttmmmm m. N - 1 symms)) ) (Vh+1 - Vh+t))
Eg-
(1+ +
H
1= K.m.j
188 V 2T
0o (1 h,t) H 22 a)4, V(s, h) and Vt E aT)(
27

---

Published as a conference paper at ICLR 2025
Here,
((s,a.h,t)=
E
(Fa.ah- -
1mmma sp+l
(Vh++ - Vi+t) [ (ss , an
k.m))) (s, =
k.mm
E11
Σ
(1
2 1
[
kkmm > 1 (P.
kimss k.m. n
1 p.m.s) ) (Viitz Virta
11 x 9H / 22
1==1 k.m.j
N
2i
12
a))
P Ps (mmm))))
X
S
V
No a) ao,,a,
Snt1
H
E13 =
PP tomid k.mss (V/it)) - V/+ (st
$ H 2116
as
1=1 Kmmm
814
Σ
(P pims a.m. (Vi++122 Vh+ ($ k2)
S H22 /2T
k,maj
(s,a)
E1s
1
P Peah - (omalee)
boofk h+1
Vi+t1)
S 2H
2c (s,
as)
8441
Then we have
P(E,) 1-022-SAB 1112 (1,6,7,10)
P(E) 2 SATip. E (8,4,12, 15),
P(E.) 2 p,i E (8,9, 11, 13,14), 14),
P(E) 2 - SAT, + +1p
and
P(())) 2 1 SATR(AHT) + 1)/Hp.
Proof of Lemma D.5 First, we will prove with probability at least SATT/ Hp, & holds. The
sequence (V (kmm))::) P. P, A V Vitt is martingale sequence with its absolute values
bounded by H Then according Azuma-Hoeffding inequality, for any p (0, 1), with probability at least 1 - p, it holds for given n a) = =n= E N that:
Σ
(+41 (kmm))..) - P. Ps Vir..) S
2H
For any hs E [K], we have n (s, a)
[T
H Considering all the possible combinations (s, a, h, k)
S x A x [H] x Th
H and (s, a)
E
Ti
with probability at least 1 - -ATT Hp, it holds simulta- H
B
neously for all (8, a, h S
A
x
[K] that:
a
(B.m.Bi.) Paian (ita)
2H2
V (3
/V nit (s)
S
n (s, a)
This conclusion also holds for for Eg and Ey as {(Ps.a, 1 (x.m..)),, [V veffi })EN is
*ht1
martingale sequence with its absolute values bounded by 2H, and ((P...
(n,m,)), ) 1
(V
8ht1
h41 ) is martingale sequence with its absolute values bounded by 2712.
28

---

Published as a conference paper at ICLR 2025
Next, will prove with probability least SATip, Es holds. {(Pa,ahh
(k.m.))i,, W1 bent is martingale sequence bounded by H Then according to Azuma-
*h 1
Hoeffding inequality, for any p E (0, 1), with probability at least p. it holds for a given
(s, = N e N4 that:
Σ
P. Ps.ah (ammdiin Pb11
Vh+1
S HV2N
For any & E [K]. we have (s, a) E 1. Considering all the possible combinations (s, a, h, N) E
S x A H P
with probability at least SATip. holds simultaneously for all (s, h, that:
x A x
X
N
Σ
Ps,a, - (l.ma)e...
I H (2N
Sh+1
This conclusion also holds for Es, E12 and E1s because of the similar martingale structures as follows. For 4 the sequence {(P 1 (k.m.)z,, ) (V)offkk))))) ) is martingale sequence with #p41
(k.m.)),, A JieN is its absolute values bounded by H2, For E12, the sequence {(IPs,a.)) 9h-1
martingale sequence with its absolute values bounded by For E15, the sequence {(P (Pss,,h
1 (kmo)), (V. Vitt))ent is martingale sequence with its absolute values bounded by S1-1
2H.
Now, will prove, with probability least 1 p. Es holds. Because of (i) in Lemma D.I we can append multiple Os to the summation such that there are Ti terms. Since the sequence {(P, "ammm a.mms, h 1 +hi1 ) k.mm)))))) h.,.mm. can be reordered chronologically to a martingale sequence with its absolute values bounded by 1, it is still martingale sequence with its absolute values bounded by 1 after appending some 0 terms. According to Azuma- Souma-Hoeffding inequality, for any p (0, 1), with probability at least p, it holds that:
P k.m. k.m.d -1 k.m.m Sh
1 (smm))))) I V2T2
.0
k.m.j
Similarly, the conclusion also holds for Eg, E11, E13 and E14 because of their similar martingale struc- h+ - -Vi+t)) Jimmh can be reordered to martingale sequence with the absolute values bounded by 18H. For El1. ..,,,,.)(VV.... (Vittt V vx+r))lmmmi. can be reordered to a martingale sequence with its absolute values bounded by 9H. For E13. the sequence {PP (.mas attmm (V++t) - Vi+ (x J..m...h can be reordered to martingale se- quence with the absolute values bounded by H. For E14, the sequence [PP..mm .akimm A 1V
tures follows. For Eg, the sequence (1+2/H))* sn Jims ah himms k.m.. (V
the sequence {(1 + 2/ 2/H) k. > 1](P a.m.s .af aimmi . s,
(Vitn(s) (mmm)) J k.m.jhh can be reordered to martingale sequence with its absolute values bounded by H
Now, we will prove with probability at least 1- S.AT (HT) +1)p, &g holds. According to the Lemma D.4 +/2 H and p + z. we have that with probability at least (NH + 1)p, holds for given N (s, a) N N that:
N Σ
V. a ( (v ke y +
Vi Ti
Ial < NV
+ Hi
ht1
For any & E [K]. we have (s, a) E [T]. Considering all the possible combination (s, a, h, N)
S x A x H Th then with probability at least SAT, (HT? + 1)p, it holds simultaneously
29

---

Published as a conference paper at ICLR 2025
for all (s,a, h xxxxxx Ax [H] x
[K] that:
N
2
Vt
X1 S
V s.a.k h+1
) +
+ Hi.
(s)
Ti
Similarly, with probability at least 1 SATT + 11) Hp/ Sffp.. &g holds.
Finally, we will prove, with probability at least - SATT/ E1o holds. V(s, a, h () is the summation for all the visits to (s, h) in stage t, which is a martingale sequence with the order assigned chronologically. According to Azuma-Hoeffding Inequality, for any p E (0, 1), with probability at least 1 p, it holds for given y (s,
N4 that:
Σ K.m.j
(Paa. - - (. shtt
(V - Vi++1) 11 [s an
k.m. b.m.d (s, a), =t] S 2H 2yc.
For any t E [Ta(s, a)), (s, (2)]. Considering all combination of (s, a, h ES x A H [+] with probability least SATT/ /Hp, it holds simultaneously for any (8, h) E 8 A H
and any / E (Ti/H Fi/H] that:
((s,a,4,0) s 2H 22 a).
E PROOF OF THEOREM 4.1
In this section, we provide the proof of Theorem 4.1 the event Mm- & and show
Throughout this section, we will discuss under
Regret(T)
S 0(1 + V MVAHHPT HY + HYM
+ M + SHH log(T) + VMSAH log(T) 5 AH /No log(T)
+ SAH (Al)) + V MSAH V MSAH' 3/ Màst #
+ 5 AH log + SH No log MSAH + v MSS log logglo (MSAH)) VD) (26)
where Es are the events in Lemma D.5 which shows that PP 1-1 &,) 2 (4SA7) + SAHTT
5SAT?/B H + 5SAT, + 5)p. Thus, showing Equation (6) will complete the proof. Before uu,k M
start, introduce some stage-wise notations. Let pr, k (s, ExrA <tt Em
ref.k (8, = Exarf <th Em
mi,k' aadv, ( = Ewiy' =1 Em Tiret Ph
m.,.
andv (s, =
Ewag' =th Em
mik' yyall h.adv: ph (s, = "Ersg= Em Mh,val
m.k' sef,
8%
)² and
N
aadv,k hh
gahn Baa
Here, mref. and gref represent the sum of the reference function
squared reference function at step h + with regard to all visits of (s, a, h) before stage (h a). and aadv, ,.adv,k vallk are the sum of the advantage function, squared advantage function, and the estimated value function at step h + with regard to visits of (s, a, h) during stage th, a) 1. Li(s, a, h) and Le(s, a, h, k), have the following equalities:
.7%
Using the definition of
Nt
N
zoo ( (s,
yefkk (emmlee), of (s,
(8)t1
vodlke (tmmm)le)) ))
(8/+1 h+1
1
adv (s, a) = --00
- veel (H.m))))))
h+1 (5
g = Σ
h+l - ( (k.m))))))
h+i
1=1
1=1
30

---

Published as a conference paper at ICLR 2025
11 (s, = Σ
h+1 19/1
1m1
We also denote
k+t,11 b/
Up
v
/21121/127t
2 (s, = 2/ 0/
zocktt /Nth11 + +2V 0% b0pl /n/ k++
+10 (1//N (1/N2+1233/4 + (c/mh 1// + 1/N N + +c/m// 1//
and
@
Q.tt111 (s, a) (s) Uh 1 / + 1 (s, (s,
(s, a) as) 1h
xe + /N + Ph
m /n h + bn 1,t11,20,,0)
For le E N+ such that k+1 > the we have the following relationships:
Pn
adv.k
( = Pa
(s,a)
adv (s,
adv (s, = = Adv,
(s)
h
nn
vall (s, = 1/ (s, (s,
val,k+1
(s, 11 In this case, we have Q + a) = Qutt111 (s, a) and @hh
(s,
a). There- = (
fore, based on the update rule Equation 7. for 1n l (s. > (s, we have O++ (s, = min (s, a), 2 a), Qh (s. a)}. Since these stage-wise notations fh prpeli maciik and pa p have the same value for different rounds in the same stage, for Ex (s. Q. a) = (
(s. we have (s,a) a) and @ (s, = 2% a). According to the update rule Equa- tion (7) in this case we have + (s,a) a) (h, a). In each stage, using mathematical induction. we can find that for any E N4. it holds:
[++ = 1 H + I 1R+1 > 1 min (.1 a). Q ( a), (x(s, (27) Qh+th (s. = [
Here, 1+1 is the abbreviation of 1 (s, a). Since Q (s, a) is non-increasing with respect to k, in the following Lemma E.1 we will give a lower bound of (s)
Lemma E.1. Under the event ni E in Lemma D.5 it holds that for any a, k) [H] x [K]:
(h(s, 2 as)
Then we have (s) 2 (s) for any (s, h, k) E 8 Ax X [K].
Proof. We first claim that based on the event &g n E Lemma D.5 it holds for any (s, h k)
S Ax [H]] x [K] that
N
Σ
h+1
S (x(s,)) Sotk (s, + 5H / (N
(28)
and based on the event Eg n E7, for any ( ES
H x [K]. we have:
Va (V (v
vorh < n a)
a) gadu (s. + 10H2 / (s)
(29)
31

---

Published as a conference paper at ICLR 2025
We will prove Equation 28 and Equation 29 at the end of the proof for Lemma E.1 Combining
Equation (8 with the event Eg, for any (s, a, k) E x Ax [ x [K], we have:
N
vi
1x15 S (s)
V Ve h+1
(e +
Hu
Ti
(VN)(s, ( (s, + V 51122 /NH2//NN a) + V + Hi)
())
Ti
"h
(s,
V5HL²
Vi
Hr (T(s,a)
=
(s)
(s)
N)(,,a)Ti
UN (s. (s,
1/
+ 5H
+ 411
(s.
(s,a)))
Similarly, combining Equation [H] x [K]. we have:
29 with the event & in Lemma
D.5 for any k
uody. a) 1
#
1x2l $ 2v
10H
+
6H
(s,
(s)
Therefore, according to the definition of 2 (s, a), for any (s,a,,,)) E S Ax [M]] x [K] it holds that:
2 (s. a) 2 lxa++ [x2l
(30)
Now we use mathematical induction on h prove (s, 2 Qi a) for any (s, a. h, k)
S x A x [H] x [K]. For k = 1, (s, = H 2 (s),a) for any (s,a, h) E S x A x [H]. For
k 2 2, assume already have Q% (s, 2 (s, a) for any (s,a, E Ax H x kk
then will prove for any (s, a, h) E S x Ax [H), (s, Q% a). According to Equation 27 the following relationship holds:
( a) = T [t = 1] + 1 > 1] min ( (s, a), 0% (s, a), Q (s,
Then for any given (s, as, E x A x [H), we have the following four cases: (a) If as. 1, then (s.aa H 2 (s, a).
(b) (s) and ()) = Q: (s, a). then the conclusion holds. (s.
(c) If t (s. a) > 1 and (s, = 2 a) = (s. + 1 val.k /nt + 5bh 1 a).
Because of Equation
D we have the following equality:
@ī(s,a) = rn(ss a) + P.P.a. V
Then we have:
(s, -h(s,a)-Qi(ss,
uh yyal, / /nt + (s, -Pea, Vitt
n Σ (vit (s ((fttma)))) P. (P.aa + Ekll as)a).
(31)
According to the definition of 1,(s, a, h, k), we know ki < k for E (s, Then Q (s. a) >
Q7 a) based on the induction. Therefore, according to the update rule Equation (13) and Equa- tion ①1. for any (8, h) E S x [H] and any i E (s) a)), we have:
big (s) max 2 (s, 2 max Qi+1 a) Vit aEA
Ai;
Va+i
(32)
aEA
and for any E [nx (s, ()) it holds:
P Pa khg
2 P. P.saa
(33)
32

---

Published as a conference paper at ICLR 2025
Combining Equation (31) and Equation
32
we have:
n
(106,a)-Q((x... 2
Vh+1 (8/411
Ps,an Vi+t) + 1 (8, a) 2 0.
( a)
n
1=1
The last inequality is because b/21 v /2H2//nf and the event &L in Lemma D.5
(d) If th (s)a) > and (s) (5, ra(s,a) un ref. /N + Pn / 84.2 (s, a). We have that
kddv k+1
@h(s,a) a) - ()(
Uh 1 /NT Ph /ng + k..2 (s, - -Pe.a V441
adv.k
N V++ (5h-1
D (Vili)
viet,, (lmm)))l))
Vn+i (5 + 1/ (8, - -Po,a V
(s)
n2 (s)
- Ps kz
En P. (V
h+1
Ps Vh+t + (),,(s)))) X1 - X2
(s) No i= P...a Viotii
(8,
E saa V
En P. Pr h+1 Pa.a Vi+t1
+
(34)
(s, a)
(),
(s,
(s, X1 x1- -2)
As V is non-increasing with regard based on (j) in Lemma D.I have:
P
Vo h+1
P n,a V Virta
(35)
( a
n (s, a)
Based on Equation 35 Equation 33 and Equation (3)g we know each term in Equation (34) is
nonnegative. Therefore. in this case Q
(s. (x 0.
In summary, prove the conclusion that Q (s. 2 (s, for any (s, a, E Sx H x [K]. The only thing left is to prove Equation (28) and Equation 29
Proof of Equation 28 and Equation
29
For any given (8, (.a.kk)SSSxE ESEXXXX (H] [K], let:
No
Xs(s,a, a, h,,k),)) = Σ
PP Prahh - (...a))..)
(36)
8/11
EN NK vee ($/+1
No Σ
Eist P. ss violke
aa(8,a,
(37)
(5,
(3,
Nol ΣNI 11
P Ps.a. kez
2
No
h+1
(Paa, Viaaaatttiii vooitte) h+1
kk(
(38)
(s.
Without ambiguity, we will use the abbreviations X3. X4. and Xs in the following proof.
First, we focus on bounding |xa|. Using the definition of oh (s, a), we have:
No V yof.kk, (5 (.mm))e))) 2 (Ei
N
(H, (s, Σ
(vret (s
(39)
No (8,a)
33

---

Published as a conference paper at ICLR 2025
Summing Equation (36)
Equation
(37).
Equation
38
and Equation
33
we can find that:
N
N
N
v, hh1
(V/t1 V
Σ P. a, h+1
Σ
P
Foo.h h+1 )
violikie)) 2
= - (s, a)0%
x1
(40)
Because of the event E4 in Lemma D.5 we know;
Ixal
s H 22 (s,
(41)
Next, we focus bounding Ixal- Using the absolute value inequality, it holds that:
Viotikzz (l.mm))e)) + as,, Va+1 Veetikee)
(8h+1
No
(lmmsllee + Ps.a vichhes 1) 2H.
(5/+1 h+1
Then we have:
N
bo (Rom))le)) ) + Paonr h+1 (8
Ixal
h+l (#h+1
(s,
im
N
(5 (5
(k.m.))le) - Poaa velkke) ($
h+1
h+1
N
S 2H
Σ
Ps.a.
viotke h+1
< 2H2 v (N,
(42)
Sh41
The last inequality is because the event Eg in Lemma D.5
For Xs, according to the Cauchy-Schwarz Inequality, we have S 0.
Applying the upper bound of X3 Equation (41 X4 Equation (42 and Xs to Equation 40 we have:
Σ V v. (V
I as) d + 5H2 (s,
Then we finish the proof Equation 28
The proof for Equation
29 similar, in which we just
need substitute (s, a) with n (s, a) and H² with 2H²
With Lemma
E.1 Equation
13 and Equation for any (8, E x [M] x [K]. we have:
V
max
(
a')
max a'EAA
Qi(s, (s).
(43)
a'E.A
The following lemma gives a viable value of No to learn the reference function Veefk (s). Denote V-EEF( (s) Vael, ( (s) as the final value of the reference function yref,& (s).
Lemma F.2. Under the event Ni= E, in Lemma D.5 it holds for any h E [H] and B E (0, H) that:
SAH
MSAH3
Σ T Vi (.. VV (5h (s) 2 3 < 5184 k.m
16
12
B
34

---

Published as a conference paper at ICLR 2025
In addition, letting
SAH²,
MSA
No 5-844
+ 16 , E (0,
g2
we have that for any (s, E S x [H],
Vha (s) H (i((s) S Vu (5) S (s) + +
Proof. We claim that for any non non-negative weight sequence fwk.m.) kmm and any h E [H],
Σ Wamm. (V% Vih) (o/. mm S 8H2 [MSA + 9 // B/SHH|/w |امس|ممعا) R,m.J
||
(44)
Here, || ma Jk.m. and |k0/|1 = E kim Wk.m..j If we have proved Equation 444.. then letting wk.m.jj 1[V (6p k.m. - V/r (8% 2 B). according to Equation (44 and Equation (43).
we have:
|W|1
Σ
V/h (s (.. - Vn (s) 2 $]
k.mij
(s (mi.))) - V/2 (/ (s)mm)) 2 3] (Vi (oh (shmmm V/. (5 (m.d)
B
k.mjj
<
8HS + / SAHl)(wll))
B
Letting = 72H2 and e 8MSAH we have:
B|W|11 - by
|| /
c 0.
Solving the inequality, we have:
b / T
+ 4,c
0 S
|ll| S
2,3
Then:
|W||| S b / B2 + 43c
+ 6² 48c
SAH
MSAH3
5184
16
2,3
2,32
8
Therefore, for any h E [H], it holds that:
SAH L
MSAH3
Σ [/ (s (i.d Vx (s m.m. 2 B) = 1|w111 5184
+
32
3
Especially, for any (s, h) we have:
(s) B, k.m. s.
[ No-
k.m.j
Since V (s) is non-increasing with regard to k under the event N & according to Lemma E. and (i) in Lemma D.I (i) (s) is also non-increasing. Before we update the reference function at (s, f).. pref&
(s) H. Therefore, the reference function at (s, hi) not updated in the algorithm, Vi (s) H. Next, we discuss the situation in which the reference function (s, h) is updated in FedQ-Advantage. When we update the reference function at the end of round k, we
33. Therefore, for the final have Σt Ekmnftee T 6 m_jj =s] No and thus 0 & Vit Vi
value VREF (s) Ved kl
(s))(ss) it holds that 0 S V V. Vi)( B. Then have V, (s),
V (s) = H or V (s) I VREF (s) < VTT + 3 under the event -= &,. Now, we only need to prove Equation 44
35

---

Published as a conference paper at ICLR 2025
Proof of Equation
44
According to the update rule Equation
13) and Equation 27 for h [H),
we have:
(5% m.kk)
max aEA
(5%
k.m. a) = ( ax
k.m.
k.
11 m. = =1] H + I [
1]
1t (5%
k.m. k.
1| H + I ('t [ohim >1]
En He,
Vn+' (8p-1 (
Th (sh an
k.m. k.
+
+ ihi (s% s.mmn an slimss)
ni (0) k.m.
ah kmmo)
and according to the Bellman equality Equation we have:
Vi (5) km.kk)) = max Qh (s%, k.m.j
aa 2 Q7 (8)
k.m.
a
2 1 1 k.m. > 1] (ru(sh k.m , B.m. + IP amm m. J Vieta)
Combined these two incqualities, it holds for any h [H] that:
(V% Vi)) m)h)
I 1n k.m = H +
k.m.m. I
> 1] x
(45)
Eis Vi ($p+1
FM.1 (s
(std Oh k.imadd TP p.pim a mim. in Vh+ti
b/
ni k.m.j.
ah k.
Vin ($
< II Tihoma =1] H + II [ > 1]
Liml
+ 25%
(s
k.m. A.m.j) On
The last inequality is because of the event & in Lemma D.5 Then for any [H]]
Σ Wk.ms Vi:) (5) h.mm)
Σ wk.m
pomm (
1]
+ 1
k.m. > 1 x
kymm
k,mi
(Vit1
Vi+ (8 (k.m-5310)
ms a f.mm.))
mk.
& (5/
k.m A.m)))
2 E
wkim (h
(46)
k.m.j
on
kym
For the first term in Equation (46). have:
th
R.m.
Σ k.m.jj
(s kom a k.md) =1]
(sh
k.m.d A ( (s,
k.m.
(8.0)
(0 an k.
k.m.d b..m..) (s, 1/ ((( (0) =
For any (s, h) E S x A H [( k.m.j k.m.)- = (s, (s, a) = 1] = 1 if and only if
an
k.m. ah k.m.j) (s, and (s. a) 1. Therefore, Σk.m. (.m.j. .ah k.m.j) (s.
= as, Because of (c) in Lemma D.I we have:
T 1
R.m.j
H = H Σ (s, < H SAM(H +1) 2MSAH²
(47)
k.m.j
3,a
Then it holds for any it E [H] that:
Σ
T k.
1)H ||m|
Σ
1|H < 2MSAH W
(48)
k.m.
k.m.j
36

---

Published as a conference paper at ICLR 2025
For the second term in Equation (46). have:
E
(Viti - Vitta) (s/+1
(k.m.)le))
Σ Wkm
i=
Iithim > 1]
(5 (s) .a ).
k.m.
(Vitss - Viita) (s/+1
Σ
mki
n whh ap m.s.
11
Σ
m[(k;,,5), = (K, 33)]
J.
W.mm +
VA
Vieti m'' )" (5/tt2
ulth:mm > 1] [l(kk, (k',m',3 ,'))
Wk.mJ
"/ (6%
k. i=1 R'mm"j"
===1 Ll(k, J., = (K', "'''m'' m'))"),, th himm > ) Vitt1 Kmm''
Wk.m
n h
k.m.J B.
k'm',
k,mn.
Let:
[ke m, J), = (k, thi > 1] 2 0,
Ww ml S
Σ Wa.mj
iisl
k k.m. a k.m.)))
(8/
and
1101000
max We Ww.me m || = W.mm S
E
Je' .'
We have:
En nh (Vitt) - Viita) (#h+1 (iamieee
Σ
m. > 1]
wk.
k k.
Wn o' (V
Vi+t2) K'ndd
(49)
Next, we will explore the relationship between the norm of fi F h.m. and fare hmm For
aa given triple (K', m' j'), according to the definition of (s k.m.J. k.m. h, k), Dnh Il(kk, m,J),. = x m and 1 <
(k', m','") ,i)), p.man
1])
if and only if (... a k.m..)
(0h K a'mm s ,
th (sh, k.m o0 k.m.. = th (sh .u
k. k.m... + 1. In this case, we have th (s) "amssahh ,ay k.m.)) > 0 and stl
kmms k.m.... n (on an
yn (sh m' 16 mm md's"). Then for given triple (K', mn,j"), holds that:
[[k,, m. j)., (K' (K, m') "n ske. >
k.m.
Σ
I (s
k.m. a k.m..) H mn Ri mm ml J'), (s (st.mms ooy chim
th (st.ms, oh ahim..)) ) + +1]
k.m.j
= y
+1
(s)
m'
ap
Then according to (e) in Lemma
D.I it holds that:
Σ 1
Th m, = (K'
1'''' .mm j'), the kkm
> 1]
Ub (st Oh
1 +1 mm
os' k Am mn'
2 H
$ 1
n/ (5 kim. .0h k.mdd)
o mm
k.m.J
yh ($% , ag
Then we have:
Eni Tlkk, m,m)m,), j)1, = (K', ml J'), k.m > 1]
2
||0| ||w||100 Σ
< (1
n// (5
k.m.J. ,, k.
k.m.j
37

---

Published as a conference paper at ICLR 2025
We also have:
nx
[ke m. f)., = (R'', (h','', n'),""), jr), t/ thomn >
|00||2
m.
n (8/2 m. k... thim 1]
an
1e m mm l.mm
[[k, m. 1). (K', ml J²)) th
Σ wk.mmi
n (5% mm an
mm 5'
k,mid
1=1 le' ammii
wk.m.
= 1|w||2.
k.m.j
For the third term in Equation (46), we have:
Σ
Wk..
m.m.. m. m.m. by R., (sh On
1[th > 1]
k.m.j
W
2H2
>1 1|
Σ
(s
k.m.J. a.. (s.
,ah
n/t (8th a mb..
k.m.
0,a
Thlssaa
2H2
Σ
II i an k.m. = a)
I a)) = Σ
Wk.mi V ())
8,0 kim
Th(aaa)
Σ
Wh.m. V yn (s, I [00 mmm, ,4 k.m.) (8, a), (s,,), =1]
2112
8,0 k.m.J
1=2
Th (s,a)-1
wkmm (s , dp m.m (3))) - (),
2H2
k.m.
Denote
q(s, a,),
Σ wk. (shi (s.. an a.miiiiy (s. (8..),,((((..)==
k.m.jj
and
Th(s,a)-1
(ss =
Σ a(s,a,t) for a)) 22
(50)
Then have:
Ta(a
2H²
Σ wk.m. 18.1 (s k.m. a k.m.d )
1] Σ
a(s,a;t)
(51)
(3,a)
kj
For the coefficient (8,, a, t), we have the following properties:
a(s,a,t) < 1oo Σ
k.m.j k.m.d) (s, a), = [+1] = |WWloo0/h (s, (52)
k.mjj
and
Th(sa))1
Σ (( = Σ Jhin
Σ
.... (8, a)
k.m.j
1=1
(sshiman an
R.m.d) (s, (s,,),1((,,0)>11
mi
k.m.j
< Σ
Wk.m.. = ||w||11
(53)
k.m.j
38

---

Published as a conference paper at ICLR 2025
Because yff (s, a) is increasing for 1 I (s, a) - given the equation Equation (50 when the weights ((5, (. a, t) concentrates on former terms, we can obtain the larger value of the right term in There exists some positive integer to (s a) 1 satisfying:
Equation 51
1g-1 ||w|l00 Σ yh
Th-
(s, a) < ((s,a) S |Wl| 00 Σ
++1 4h
(s, a).
(54)
and
|
00
Σ
yh
++1 (s, 2 a))
t=1
Then according to Equation 52 we have
Ta(a,a)-1
10
Σ
q(s,a, a VV ().s)a)
Σ
|لااام ++1 (s.
(s))))
(55)
v (s)
Since 40 S (T)(8, 1, according to (e) and Equation
16 in Lemma
D.I
have:
+ (s,a) V y (s) - (1+ 2 H Voh S 3(1 yh
VH (Vyi(s,0) - v (s_a(s,a)) (56)
If to 2 2, we also have:
to
to Σ
||||| 10
Σ
yh
(s, (s,a)
++1
2 (1
||wl|a
= (1+ ||wس|| 1oo v (s,
H
H
|||||| | y (s,
(57)
2
The last inequality is because (f) in Lemma
D.I
Then according to Equation holds that:
fo-1
|| Y/a (s, a) s 2 2||||
yh (s,a) S (g(
Applying inequalities Equation 56 and Equation
57
to Equation (55). we have:
Th (.fs.a)-
Σ
a(s, a. t)
1
w as
< 3( + H
H
VV
V (s,
=3(1 + 2
H 1oo
< 2 2H (
Here, the first inequality is because of Equation 16 The last inequality uses Equation 57) and 1 + # < 3.
4o4 = 1, then g(8, a) S ||0||20 (s) Therefore, according to Equation 55
we have:
(1(
| so v (s, a)
Σ
a(s. () S (s(,,0)
vh(s,a) S
Based on (c) in Lemma D.I it holds:
(1(3,
a(s, () <v( 2 wwlll a) s 9 2H 2 wolooolss a).
39

---

Published as a conference paper at ICLR 2025
Therefore, for any to $ (s, defined in Equation 54). have:
Th (=
Σ
a(s,a,t),
9/2f1 2H (ll
(),
Combined with Equation 51 we have
Σ J.
W
1 m.m. k.m.J (5%
an
1 - 18 H Wllloo Σ a)
8,0
s 1 S |
(58)
The last inequality uses the Cauchy-Schward Schwarz inequality.
Based on Equation 45 by applying Equation (88 Equation
49 and Equation 58) for any E
[
we have:
wkima (V/2 (s < 2MS 2MSAH Wwl + 18 SAH* wool |w|l
k.m.j
Σ
wk.ma (Viti Vi (s
(59)
k.m.j
where |00|| loc S (1+ [] and ||ا|| = ||w/|2-
Using Equation (59
with induction h H, H 1, we can prove that for any h [H]:
Wkmm
(5) k.m.)) S Cn (2MSAH2 W + 18 /
(60)
k,m.j
where Cj = (1+ + H )1 + 2 H
H 2
Note that C₁. S 4H, based on Equation 60 it holds for
H
any h [H] that:
Σ Wk. (V - (5 k. S (MSH W + +9 A/SHHellae | I (w|l)). J.
Therefore, we finish the proof of Equation 44
Next, we go back to the proof of Equation 26 In the following content, En. is the simplified no-
tation of EK EM In N². n L,, 4 represent simplified notations for N (s), R.m... aq m.m..)). k.m k.m. h) and I (s..m. .a k.m.j. .hh h. respectively.
n/, (s k.m.J. k.m. ,0 k.m.... ), (. a
For [H + 1]. denote:
(VB
Vi+) (3 k.m.).
M
c
V
ViJt
(s k.m.).))...
j=l
Here, 5//1 Ch+1 = 0. Because (s) = sup Vi((s), (s); we have of S Sh for any h E H 13. In
addition, as (s) (s) for all (s, h k:) S [H] [K], according Lemma E.1
we have:
K
Regret(T)= = Σ (V - Vi*" (sk.m))) <
(v* - (s (s).).)) = Σe
st.
k.m.j
R.m.c
km
Thus, we only need to bound
ΣK st. Let:
(
dk kim k.m.d
1
Nº
(Veot.ke, V-RET
1h+1
k.mid k.m).)) (6 ax
F
m.m a mom
(61)
i=1
40

---

Published as a conference paper at ICLR 2025
M kk
T (8h mime ,0 aay biiman > 1]
m h+1
n (5h k. .ah mi)d)
IP k.m. son
1 coimisles
h+1 - Vitti,,
sh+t
3
(62)
M
1h (sh
k.m.d, (limdd > 1] ah
P Pogmss
(Vitt v+t1) (63)
h+1
an
m=
where 1 HH+ =
& fH+1 0/i+1 = 0. According to the update rule Equation 27 we have:
1/ (6 k.m.jj = max
kmm .) = (5 k.m.. k:m.))
(5h
atA
T
m.
h
1 H + I
k.
h
> 1] @t (0/1
k.m. k.mdd Ohh
Eist No Vhit (8h+1
< I
1] H +
kmm
> 1]
ralstimms on miid
No (sth ah m.
n Diel
(Vi+ti vietier) ($/+11
3 (s ah d))
nh an m.
Also using Equation DT we have:
Viri (sh, (m):
= 1 (sh (m ahmm 2 Mpthim > 1] (ra(sh.mm k.m. og ch.mm..) + TP m
m. no Vhttt
Then with Equation 30 holds that:
M
Vi vx²") (oh m)
m=1
j=1
miik
mi.k
folmmss =1] 1 + 1 f. > (sh aa
k.m.)))
Σ
11 Σ
> 1]
j=1
j=1
Σ
No
&ee (s (Bamm))ee)
Σ v
(vitis - n+11 (8/+11
(h.maill))
PV
x
(s kimm .ah k.
( k.m. an ki
M n mi
M n Σ
2 Σ
p.amm 1] + 21 [ [chmmm > 1] 84.22 (s k.m. a dkmmid)) +
m=1 j=1
Σm Prokke h+1 an m....
Dim IP ( (viiss viothen k.m.j.
TI Tihmm
1]
PV
(64)
(o
k.m.
n/y (1
.an (.mm
Here P is the simplified notation for IP. simis
o a.m.s A.- Because the reference function is non-increasing
sh based on (i) in Lemma D.1 we have & (s) 2 VREE (s) for any s E S and any positive integer i,
P. k.m. bim 2 1+411
2
P gums ki A h+1 and
VREF
b
Σ
IP aomm kims lot1
sh on
P kim Amm. . h+1-
(65)
( k.m. ap B.m.d)
.a
According to the definition of 1 wht tht th Ph+i and Equation 65
we have:
M
IP gimss aftms in Viot
Σ
12 i=
ref, IP yom.d .ah kimis h h+1
Σ
Rimid
[1]
1]
Eisl
k.m. k.m.J) Nà (5)
k (3
k.m
k.m.d )
m=
,6,
a
S w/
(66)
41

---

Published as a conference paper at ICLR 2025
M
n mirk
E i=
P v m.s on m.m
N (Vitti Viita)
Σ
I
1
an k.m.) n (5%
k.mes
m=
M n mik
Ei (Vrti
VVitt) (sh+1 ((ttm)ll
c +
I p.mm
1]
(67)
n (8)
h. uh m
j=l
and
M mede
Σ m1
1
k.m. h
P gumis mmi (Vitt1 b
(411)
oitt +
Sh+z
0
(68)
an
Summing Equation
66).
Equation
(67 and Equation (68). we can bound the second term in Equa-
tion (64) as follows:
M
D PV
ii=l IP (V vietiee)
T
h
m.m.
>]]
N (8h kima a
n (0% kimoa , a.im
PV s
m=1
M mm
i= (vitii
Vo+1) (ltmmi
($n+1
ΣΣ
+ wh+t + thits + thh + Sh+11 - -8hi11-
(5/h m.m. ax d.m
m=1
Together with Equation
64.. we have
minkk
M
22 mink
1 k.m.j 1]
H 2TI Trh.ma > >1]82/
(5.22 + Σ T I. 1]
f=1
E1
h+1
Vn+t1) ) (#/+1
(R:m.)ls) / k.
+ whit + chtp + thin + Sh+t - 5
(1 k.m.J
Summing the above incquality for tt = 1,, 2, .., K, we have:
K
( k. = 11 H + 21 (th tii > 1| b% (5% k.m.jj k. + Σ filim > 1 x
k=1
k.m,j
k.m.j
(Vi+11 V²) (s
K
Σ
(wh+1 + cht1 + ohtt + Gh+1 - 11+
(69)
(5 (.. ,ah m.m...))
k=1
We claim the following conclusions:
Σ
T
[
=1] 1] H 2MH
k,m.j
Σ I R.m.j
[ I
>
(viLs
Vitt (8ht2
(lmm)ll aq k.))
(1+
2
K
8
(70)
The first conclusion has been proved in Equation 447), and will prove the second conclusion in Lemma B.3 in the last subsection. Applying the two conclusions to Equation (69), it holds:
K
2 < 2MH2SA (1
(Wh+ + + + Oh + +hh+1 5h4z)
H
km
k=
km
+ 2
k.m. cn
> 1
kk.2 k.m.J. k. (s)
oh
k.
K
K
< 2MH + (1 +
H
Σ
Sh+1
+
Whe+ + this + ohin)
k=
k=
+2 Σ
k.m > 1] cR
t (s
k.m_ k.m.)..
an
42

---

Published as a conference paper at ICLR 2025
Here, the last inequality is because 5%+1
Sh+1- By recursion on H.H 1, 2.... 1, with
0, we have:
k
H
K
Σ
Σ
(1+
2
2 1 +
+
2
2
3 + chtt + oh+1)
H
H
k=1
h=1
H
+ 2
(1 +
1 h
k.m. > 1 2 (5% Ob
k.m.J. k.
H
#=1
k,m
H
K
- S8MH +
(1+ +
h 1 (wh+1 + c + xh+t1)
H
1=
18
k.m. h
> 1] 2
k.m.j k.m.j) ah
1= k.m.j
H K
2 nh ( + chit + oh+2)
= OMMH SA+
(1+
H
k=1k=1
I k.m. 1] (s (s
h
($
k.m " m.m.))))))
(71)
h=1 k.mjj
Here, the second inequality is because (1 + 2 2 < (1 + ) S e² < 9. Based on the Lemma
Lemma
E.5
Lemma E.6 and Lemma E.7 provided in the last subsection, have:
H
K
2 h-1
h+1 SO
H
1=1
"
K
ΣΣ (1+
2 h-11
H
Eht1
k=1k=
K
2 h- 0h+1 S OOH
ΣΣ
(1+
H
11
Σ
ΣΣN
I1
kom
12.2 k.m. A.mmdd z 1]
1==1 J
o (VSAHPTIL+ /BSAHTT /B'SHTTH + + S V logog(T))))
Inserting these relationships into Equation 7I
we have
Regret(T")
I 00((1 -WSPPTT + H /Tllog(( + SAH 4 + SH No (o)(T:) AH No
(M:) MMAH"
x (((1+ 3 / H.
+ H Io
+ +M + SHHN log(T) VMSAH logSA) / 5 AH / (og(T))
+ SAH 2 (Mo) M /1 MSAH V MSAH / M s A H 2
+ 2 AH 3 No
SH2 No log(M))H)) + VMSAH? log MSAHH))H)))))
In the last step, we use Ti < H) + MMAHTMMMHHIE H + according to (i) in Lemma D.I This finishes the proof of Theorem 4.1
43

---

Published as a conference paper at ICLR 2025
E.1 PROOF OF SOME INDIVIDUAL COMPONENT
This subsection collects the proof of some individual components for Theorem 4.1
Lemma F.3 (Proof of Equation (70)). Under the event 15 &i, we have that Equation 70 holds.
Proof.
En ph i= 1]
(Vatii - Viita) (8h+1 (iume
E T
oo k.m. .ah (iitn.t)
k.m.
(vitii -Vita) ($ (mmmei
II po >1 1]
Σ
[[kkm, . ml, J'']
n k.m an mli
k. 2=1
(V - Viitz (o2h mma
E
1[(k, m), (K, m',, I'), kkmm >
n (8% k. k.
k. mm oj' 1=1
a
(Vhtt - Vi+ta (5 mi S'j n (6( m.
Σ
Σ
m. j). = (K ,m 1',, thimm >11 m,,k,
, k.imen
W ml ot koms
(kk m. S). = (K, m', t') mim =]] n (5) k.m. .a% k.))
(V Vitta)
K'mma (1/41 J.).
W mm
A.m.j
For a given triple m'), according to the definition of 1,0% h.m. k.m. -i, k))
, ,at h.m. if and only if (sh , Oh
En l1(kk, m,j)i,
= 1','''j' j'), h k.m.
> 1])
k.m...
(0% H' un' o' aat s'm'n'
and (8 k.m. b.mds) = 1h (0) ( aah k.m..)) + 1. this case, we have
, ,
nh k.mdd an m.
yn (sh miii is 1 mn and
On
Σ k,m.j 1=1
[lkk m, 9). = (K,m', ,J),, th kkma > 1]
Σ
1 [sh
k.m. aa k. = (5%) V6 mn's Mmd ml J'), the (ottim ,a m. = th (.mm
Shh
o0 k.m ) + +1]
k.m.J
y/
+1
(sh
ml ss d K.m
K
m' S').
Then according to (f) in Lemma
D.I
TI (k, J). (K, m',)"")" J'), mn > 1] n D
1h' +1 kt mn' ,'''5')
yb (sh
, ah
2
$ 1 + H
n/t (/h(stt ah (..)d
the
k.m.j
Un (sh .hn
Therefore, since ViL 2 Viti according to Lemma
E. we have:
mi Em
(Vitti Vā+t) (sat1
Σ I [chima. 1]
n (st
k.m.d aa b.m.d.
$ (11+
2
Σ
(Vht1 (5 mm 5')
H
kmm .
K
2
= =(1+
h++1
k=
44

---

Published as a conference paper at ICLR 2025
Next, we will give lemmas on the upper bounds of each term in Equation 71 Lemma E.4. Under the event Eg in Lemma D.5 it holds that:
H1 K
2 1
(1+
Wh+ S 0 H Tog)o((T) H2SN, log(T))) H
h=1k=1
Proof. For any (s, h k) E 8 [X] = D (8, a) 2 No. the reference function No. since the reference
v (s) is updated to its final value with (x)t(((s) = VREE (s). If N7
function is non-increasing and V/y (s) = H, we have 0 S Ve (s) - - (s) I H. Combining
two cases, for any (s, h, k) S x [ x [K], it holds that 0 Vidl (s) VR (s) S (s).
where (
(s) < No) is defined in the event & in Lemma D.5 The conclusion also holds
for h = H + 1 because #+1 (s) H41 (s) O. Then for any (s, h, k) E Ax [M] x [K]
VREF
we have:
0 P. s,
(Vrtt
VRE h++1
S HP S
(72)
Applying Equation 72 to the definition of 1/ Equation (61
we have:
K
hh+1
1=
Σ
I [ch. [1]
En
iill
No
P
k.m k.m. o
ay m. nn N+1
VRRF)
No (8/
k.
Nk
i=
P
mimms aaly ti i N+tl pp
HHH
T h
1
Nk k.m.j O (.
k.m.J
kii mims m d h41
(E o I[(k,,,)) = (K, mmmm'"))))) i'))
.
I [
i== #
NK k.m. .0h abimddd)
k.
En Il(k, 5, = (K' m', j'),
the m.m > 1|F
ub tims te S,n Ak h41 W ma
H
k. l mr .5'
.h
According to the definition of L,(shims, N.mw .h). for a given triple (K, m'), (K,''',' j"), th thima
an
EiTh NK [[(ks m. m),
if and only if (shima oh s.mdd) k.m. < ( kmj
1
(sh m' 3' y' ('m") and S th (5h kmm ap
aah J.m.).. Then we have ,a
ah V mn a. K'm'' J'). For > iie (oh jkms 18h xx
m'm'
m'mn a' ) 2 1, we also have:
.ah
N
Σ k,m.j
[ (ko, = (K', (K','', mn). ( m'm's e &' mn'dd =t]
=E II (sth
k.m.j , ......) = (sth m' K m' )
2ht (5) m' a Kmm'd
= =t]
dh
k.m.s
vf (5%
(73)
Let:
Mm
I[(k, m. J.. = (k'm', mn),""), th fims > 1]
( kk smm s' r ml.3" 3')
R.m.i
oh
Then, since (1 + 2) Jh- < (1+
+ H1
2) < e² < 9, we have:
K
Σ E
(1+ 2
2
wh
wh+ < 9H
Σ
Σ
We yn yn mi at af st A
(74)
h=lk=
A=1 W Mmmm"" J'
45

---

Published as a conference paper at ICLR 2025
Applying Equation 73 we have:
L[(k, m. (k,m',j')
We m 33
Σ
I I
K. mn o . ) :]
NE (5 ",m'' w¹' _u4 m.
k.m,.
t +1
[[(k, m. = (k', S'mm,, m'm5'))] mm ot' k. mm
t (sk
k' .''
K m' "n'r ==
.aa
Y (5%
k.m.J t=th +1
Th
Eams Dis
[(k, = (K', m ,J")) thi (5%
K. mn
)===
= 1)
: -hp
1 (5
1 mm S')
a
(= +1
Th
1 (5))
K. .m of K.m mi
On
Y (sh
k,m "²)
ah
f=
According (f) in Lemma v (s, a), we have:
D.1 for any (s,a,h) E ExxAx Ax [A, L E ans, and S p s
2
(s,a ()) (2+
H
Then it holds that:
Th
yi (5)
m J H and'
an
Wemme
Yn (0)
mmm
ag
W mn
t= +1
Th
w/.
1
(=
+1 p==1
Y!
(5h1
ke see ot' x m'mmJ'
ag
2
Th
vi.
(2+
H
yt-1 (s/ (mm..mm)) '5' p.mm s²) +
(=rr)
p=1
h
an
T2 1
2
$
(2+ +
4(log(Ti) +1).
H
1=1
Applying the inequality of the coefficient Wi ml of to Equation 74p. we have:
= K
2
+
H
k
Wh-
k=1
k=1
991
Σ
Σ
WK St oy
mi of m' a W WazloKamn'd
h= lo' mmm 'i'
H
< 99 ((log(Ti) + +1)
Σ
Σ
P
1ot (5 K'm'
K
h41 )
h= le' mm o
11
= -66 (log 1)
Σ
Σ
(s
h41 + (P
kim k.m /
1l kmm))
2btn (s
aa
k= k=lkim.
< <3HH((o +1)
ΣΣ
M (o + 2TT
(75)
k=lkmmm.
46

---

Published as a conference paper at ICLR 2025
The last inequality is because of the event Eg in Lemma D.5
Next, we will bound the term
E Eam. 2 (3)m))) in Equation 775
We have:
H
H
Σ
Mht1 (
1 k.m.y
Σ
k.m.j.
=
htt
A= k.m.j
hm k.m.j
SES
H
Σ
(
k.m.J = s) h/11
h= NES k.m.j
H+1
(N)
< No. 8h
k.mo =
(76)
h=2 sES k.m.
For any state (s, h) E S x [H] and k E [K]. there exists the largest positive integer kn such that No (s) No. Then for any h HH + 1]. it holds that
Σ (s) < No. sn kmm = s = Σ l k k.m
S ko,
k.m.J
ko
komw s]
8h
mi
I
k.m.
8, a
k.m.J
aEA
(s)
(77)
However, according to the definition of No (s), we have:
No > Nok (s)
Σ
Noo (8,
a) 2
Y
(s, (s, 1]
aEA
aEA
(s. 1].
aEA
The last inequality is because of (f) in Lemma
D.I
Combined with Equation 77 we have:
Σ (N)
No,
k.m.j 6n
=s] s]
k.m.j
Σ y (s, (s. (s, 1|+
Σ
ytt (x))) = 1]
(s,
aEA
aEA
< 4N, + MA(H 5
(78)
Here, the last inequality holds because B H. Applying the inequality Equation tion (76), we have:
78 to Equa-
#+1
Σ
(
k.m. <
Σ
Σ
5No & 5SHNg-
h+11
h= 1 k,m,
1=2 #ES
Therefore, we bound the term IH E km N (s k.m.))) Back to Equation 75 we have that
K
Σ M [1+
2 2 + < 36H (log(Ti) (5SH + 22T
2
H
=
=H - No log(Ti))
47

---

Published as a conference paper at ICLR 2025
Lemma E.5. Under the event Eg n E1o. it holds:
2 gh R+1 s So (VSSAHTT SAHA(M)) (M)
Σ h=lk=1
(1
H
Proof. According the definition of th Equation 62
have:
K
R ii=l
P
pammi a mim. n
1 committee Sati
(Vitt - -Viit)
Σ
> 1]
h++1
n ( m.m.
1=1
k.mot
mm ) (iiti Vi+t))
Liel
PP
kims as
kim. n
aht1
n (5%
ti ah k.
x
kimid W "mm
I (kos m,,, (K', m',, J'), t/r k.m. > 1]
Enh ul(ks Je, = (K', m' J'),, ty
k.m.
E
n (5 mimid an k.m.s)
x
W mi k.mm.
P k.m. an .h
( Vitt).
(79)
For a given triple (K,mL, according to the definition of 1 R.mm k.m. h k)) ,
En [l(kk m,j)i, = (K'm' j')) = if and only if (s% kmm. k. + 1. In this case, have n (sh. (s an 1h k.mm ahh
: ob ab = (oh H.m m' Sh
K mm mil''
and th (o .ah ckimm.) ok' & Nim' m' and:
k.m. s.m.d
Yh (sh an
Σ k.m.j
[(k, m. (K', ml, ,")) t.himma >
= Σ T [(s
k.m.
k.m.J) = (8% ml
W mn S'), 1 < 1n k.m.
k.m. k.m.)) + th (5% Ohh
Oh
k.m.
at' +1 kml
(s
m' Mim's mm's' J¹).
= 4/
Let:
y(s, a h,t), = (1+ 2
yh-
(s,
- -1- 1
H
y/ (s,
H
Applying the equation to Equation
79 it holds that:
H K
h-
h=
Am
H
rk' +1 H. mi
m
Σ
Σ (1
h-
(sh
Op
H
th
m Uhp
h=1 F. m. 35
Ub (8h
(Vity
1441 Vitti)
(80)
H
k.m. kmm h th) PP p.amss aftmms J 1 (mm))) ) (V Vit+t)
y(
.hp
1=1 k.m.j
H
(1 +
2 1
2
Σ
(P (Paa, - 1 (mm))) (V -Viitt)
(81)
H
k.m.j
48

---

Published as a conference paper at ICLR 2025
The term in Equation (80) is summation of mon-martingale difference, and cannot directly use Azzuma-Hoeffding inequality to bound it. Therefore, we split the term with a constant coefficient 1 + 1. which can be bounded directly by Ezuma-Hoeffding inequality. According to the event &g in Lemma D.5 we can bound the second term in Equation (1) with 18/1 /2T
We claim that for any L E (8, a)], it holds that 1y(8 a, h, 6) < 9 with the proof as follows.
According to (e) in Lemma D.1 since (1 + ) I 9, for any h E [H] and I - (s, a) - we
have 0 S y/s, a, h, t) _ (1 + H
h-1
R S
9.
Fort = Th(s,a) 1, we have -9 < -(1+ ) 1-111(1 -1+
H.
#) S h, Tr - 51 H
)
9 For - (8, a), since Ta+l (s,a) a) 0. we have H H.
S
(s, h, Th) = -11 31+
#)
E [-9.0].
Now we will deal with the first term in Equation (T:
N
ylokims
k.min h, thh (Paz (Pop.ms mm -1 (mmms) ) (V Vi+t))
Hamis
Σ
E
v(s,a, t/)) -
- 1
(mmm))) ) (V/+t2 viit) (00h m. .a dbimeid) = (s.
8,a,h kam
Ta(o,))
Σ
a(s,a,h,t Σ
(Peaii - -I (mmm))
(Vi+t2 - Viitz) x
=
sb+l
8,0,h =
kima
T [8% d
k.m. " k. (8, (8, = =1]
= C1 + C2 + C3,
where
C Σ T Σ
u(s.a,h,t))Vss,.hhht
5,0,h 1=1
C2 Σ
IV 1).
s,a,h
C3 = Σ a(s,,,h, (s,, 8,a,
Here, as, = E J (Ps.a.h 1 k.m. (), which is defined in the event Eo in Lemma
(V 1 [[( (. of .m. as)
*h+1
D.5
Then based the event Eιo, have:
(Vs, (ls,a,h,1) < 2H (s,
Since lu(s, f)) I 9, it holds that:
(, 2
Th (x,o))) 2
G < Σ
(,s,a,h00l (V), 18 Σ
h.
V2
s,a.h
s,ah
t=1
Because of Equation
(6 in Lemma D.I
we have:
T-(s,a)-2
C < 18 Σ
(VYr(s,a) - -V (s,aa
s,a.h
54 Σ
v /T (s,a)
8.a.b
< 2H
SAH Σ (s,
3.a.h
0 (VSAHTTi
(82)
49

---

Published as a conference paper at ICLR 2025
The second inequality uses Cauchy Schhar- Inequality. Similarly, it also holds:
C2 -
Σ
as, 1)1 (s, (h(sa)) 1)1
8,0,
Σ
9. 2H 2/h
(n(x.a) (s,
8,0,b
S 18H 2SAH
yh
Ta(a,u) -1 (s, a).
8,a,h
- 26H
(VSAH 9MSAH + 1) + 4SATi4
(83)
S 0 (SAH (M + VSAHTT.
(84)
Here, the third inequality uses Stuchy-Schwarc Inequality. Inequality Equation 88 is because of (h) in Lemma D.1 Similarly, since y(s, a, t. Tx) -(1 + #1 ) 11), we have:
C3 5 Σ (1
2 111 (v, H
s,a,h
Tu(o,a) (s.
< 18H
21hh
8,a.h
< 18H
2SAH
Ub
Th (x,0a)
(8,
s,a
0
SAHPT SAH (M1)a).
(85)
Here, the last inequality uses Cauchy-Schward Inequality. The last inequality is because of (h) in Lemma D.I
Using the upper bound of C Equation 82 Cg Equation 84 and C3 Equation 885
can bound
the first Equation (81) with O SAH SAH 2)) Then combined with the event
Eg in Lemma D.I it holds that:
K
2 h (1+
h+1 (VSAPTTii+ SAH (M1)+).
H
1=1
Lemma E.6. Under the event E₁ in Lemma D.5 it holds that:
H
K h
ΣΣ
(1+
th S (HH))..)
H
Proof. Based the definition of oh Equation
63 and the event En1 in Lemma D.5 we have:
2 21h-1
(1+
H
Σ
(1 + H
2 h-11
k.mmm. >
(P hims .0
kimis No (mmss)) h+4
(Vitz virtt)
h=1 k.m.j
< H6 /TT (HH)T
50

---

Published as a conference paper at ICLR 2025
Lemma E.7. Under the event N Eg in Lemma D.5
we have:
11 cn
kmm
1] 2 (sh mis. kmmd) 2
0 (SAHTT1 v L BBSAHTTiL++ SAH'T AF V
Proof.
k.m.
1
(5
ab m.
A=1 k.m.J
geef ( (sth m.
Uh m.mod
Σ
I
Jumi
V
No k.m.d an m.d)
2
>
>1]
x
k.m.jj
R,m.jj
aadv, de co ap b.m....y )
10H
[ hima k,m.j
1]
n (sp
m.m. ah k.
No.
h
n
(86)
Next, we will bound the first term in Equation
86
Based on Equation 40).
we have:
h+1 ke - (Xs + X4 + Xs)
V.
A
(s, a)
(87)
(s,
According to the upper bound given in Equation and Equation 42 we have:
2c
2
No. (s, a) bxal = 2H²
(s, (5 Xal S 4H²
(88)
(s,
Since & (8) V (s), we have Ps.a, Vef 2 Ps.a, VREE Then according Equation (72)
using the definition of Xs Equation (38). it holds that:
EE Praa, V kiee 2 (s, a)
N
1x6l = Σ
Pa h+1 veothee))
PP Ps,. vrotkee)
2 No (8, (Px.a, V/REr
N
Σ
(P V/tt1 voofkee
2 )²
(IP s...ahh REFF 2]
< 2H
Σg
Veeekee h+1
Ps.a. V
N
< 2H²
Σ
P Ps.an
(89)
The last inequality because of Equation have:
According to Equation 766) and Equation 78). we
Aut1 (8h+1
< Σ
(
kmm))
Σ ΣΣ
R,m.j (N)(s) < No. h-1 = $ 5.5NN.
k.mj
#ES k.maj
(90)
51

---

Published as a conference paper at ICLR 2025
Because of the event E12 in Lemma D.5 and Equation
900
back Equation 89
we have:
2c
10SH
X S
2
(91)
N
(5 a
N
a)
(5,
Applying inequalities Equation (88)
and Equation
(9
to Equation (87)
have:
(v (V
retk 1/ je
(s,
h+1
10SH (s,
12H2
(92)
(s,a)
(s,a)
For any 8 S. VictA (s), we have aaa v 2 (IP
s,a k+t1) Then:
Σ No Eisl Vaan(( (s)
N
h+1 1akkin - Ps.a (V/+1)))
Ve (V/+1)
(s,
2H
<
h+1 (V
N (5,
(93)
Because for any S, ()
(s) 2 n (8) 2 (s), we have:
0 I ve (s) - ( (Vi (s) V
(s) + (Vet1 - Vi (s)) (s))
If A (s) 0, the reference function is updated and have h+1
()) (s) (s) S B; if
1 (s) = 1, then we have V (s) (s) I H = HA (s). Therefore, we have:
5 V (s) Vitta (s) S H +.B.
(94)
Combined with the inequality Equation (90), we have:
Vook (k.m))er)) ( (k.m.ilee)
H 1 (k.mJiie)) + 3)
h+1 (s/+1
i=1
< 55HHN, + (N,
Based on the event E1s in Lemma
D.5 applying the inequality to Equation (93). we have:
Σ Nh Va (V (s)
h+1
20SH2Ng
2
+ +213 4H22
(8,
N (s,
and then back Equation it holds:
> (s, S VaannVVita) 20SH2
+ 18
-2HB.
(s,
(s,
Therefore according to Lemma D.2
we have:
k (.m. .ah k.m.))y y Uh (o)
1 Jkmmj > $]
V
NK (5 R.m.
.ap k.
k.m. on k.mis J (Vitz)e )a
2
V18H2
2H
N*
N
(N
N
h= 1 k.m.j
> 1 t/
Σ v Vasah (Vi+ (s. a)u+ No SAH log(T;) 23 V18H2 SAHT,
k
+ 2H SAHT,
SAH
Σ
Vs DY (s. + 205 AH² Noolog(()) + A4
s.a.k
(95)
52

---

Published as a conference paper at ICLR 2025
In the last inequality, use Cauchy- Schwarz Inequality.
Next we will bound Ea,., Ve a (Vi+i ) (s, a). Because v=+ 0, removing the term Ekm (s we have the following inequality:
H
(P Popm (ap
k.m. N (Vi+1)²= Vn (8hh
h=1
kmm.
H
( koms m. (Vi+1)2 Vh+1 (12+1) 12)
1= R,mm.
Because of the event E14 in Lemma
D.5 then we have:
H
P Joma a n (Vh+1)² Vr (o S H2 22TTu.
(96)
A=1 1 j,m.j
According to Equation
IT. for any A. have:
(x) 2 (x) = (s + P. Vh++ 2 Pa V
Therefore, we have:
H
E (st (p k.m. (V
kymmi
(Vi(s + kimss ax k.ma N (Vi+ta) (s (. e.m. on k.m.s (Vi++))
h= k.m.j
< 2H
Vh mm - P m.m m. (Vn+1))
oo
k.m.
2H Σ (ol + 2H
Viita (oh. TP mi .a k.m. (V v1+1))
k.m.j
h= k.m.j
< 2HT, + 2H 2T
(97)
Here, the first inequality is because V (sh. P P.mms s.m AA (V < H. The last step is because of the event E13 in Lemma D.5
Summing Equation (96) and Equation (97 up, have:
Σ Va (s, s.a.h
Σ
m.. (Vr+1)
m.m.j
P k.mi k.m.
(Vi+t))² (PP
A.m. k.m.d
(Vitt)))
6% ,a
h= k.m.j
2HT, 3H² /T
Applying the inequality to Equation 95
we have:
Jef. k.m k.moddd )1 U1 (s), ,ap k.m.
(
Jimi >1] 1]
( ahp k.
V 1 L 2 V2SAHHT + 205 AH / (
+ 6. BSSHHTT
=0 CO(VAAHHTT..
(SSSHTT,I+SHHTT + 188AA AH² /No
(98)
53

---

Published as a conference paper at ICLR 2025
Now successfully bound the first term in Equation (86). For the second term, according to the definition of oi (s, a), we have:
n
(5 Oh (im... ot.m.)op
to k (s% m. an sl
V (sh+1
(trmmnli.) )² (sh+1 (ltm....)) - (
i=1
The last incquality is because for any S, Vaoti (s) 2 (s) 2 (s).). Using Equation (94) and Cauchy-Schwarz inequality, we have:
n
le gadv. 1/
his (Rmm.)))) H (8/41 +13) +/3)=
2 2 Σ
H2
1 (8/+1
Ni; (1/tmm)))e)) + ) (99)
i=1
Similar to Equation
900. we have:
1 Σ
Ah (5 kmm)) S <5SNo.
1 (8h+1
k.m
Back to Equation 199) we have:
og (s
mi k.m.d)
10SH2
+ 2,3
an
n (5/
k.m.
,ay m...
Then using Lemma D.2
have:
k.m.d yoT Uh aadv, (shom an
I To > 1
n 1
kiman ,0 b.mdd)
h= k.mm
11 Jomm 1n
1]
VIOSH-No4
2
< 2
( k.m.J , ,ah a.imss
(s
k.m.J k.m..) ah
1=1 k.m.j
< 4v 2 1550-10 log(T:) + +2V28L 4V2H
Σ (
8.0,h
< 40/25 AH / log (Ti) 16 BH VSAHT,
= @V AH v Not log(T)))
(100)
For the third term in Equation 87
according to Lemma D.2 we have:
H
k. h
1]
I 44
Th (.mm
(5th
, a. k.m. 1
J.ma k.m.yy Nk (8)
b
A=1
k.mjj
a
s,a,h
16SAHT 13,
H
k.m > 1] 4
< 24 17 3 Σ
Y Th (s
k.m.j
, aap m.)
n (
k.m. a,
k.m.j
k.m.
b= 1.
k,a
32SAH T
8
ΣΣ
ch
k.m. >1
< 4s Σ
Dog(Y (s
k.m. S.m.
Nk koma komm) a
k.m.j)
k,
4SAH (T)),,
54

---

Published as a conference paper at ICLR 2025
and
H
m.m
> 1]
1 8HL
log(Yn
( (5%
kmm.s kmm))))
,0 k.
n
8,0,h
& log(Ti)
Summing the four inequalities, we can bound the third term in Equation 887 with:
o (SAA SAH log(T)))
(101)
Applying the upper bound Equation 98 Equation (1O0) and Equation 101 to Equation (86).
have:
Σ
TI T. 1] 8/ (5% (m Oh m.m.
R=1 R.m.s
(VSAHPTIL+ /BSAHTTIC+ S + SS
No
F PROOF OF THEOREM 4.2
Proof.
Because of (c) in Lemma D.I we have:
Th-1
12
(s, 2 Σ as Ea+
1 1-1 1'
Σ
MH²
1 Th (1
1
H
H
s,ah 1=1
8,a,h
1=1
s,a.h
The last inequality is because u (s, 2 MH according to (c) in Lemma inequality, we have:
D.1
Using Jensen's 's
E(+
1 1mh- SAH(1+ H
1
H
s,a,
Therefore, holds:
E
f 2 MSA
MSAH3
H
This indicates that
log( log(1 + H
MSAH +1)
Σ an < SAH - SAH
(102)
8.0.b
Because Mayn = TRUE, in each round, there exists at least one triple (8, a, h)) such that the triggering condition is met on it, the total number of rounds is at most the total times of triggering conditions met for V(s, a, h)) E (S, H). Next, we will discuss the times of triggering conditions met for each triple (s, a, h). If the triggering condition for (s, a, h) is met at round k, the increase of visits to (s, a, h) is between of (s, a) and Mc (s, a). We will discuss how many times the triggering condition can be met most in one stage for each (8, a, h) (8,A, H).
1. In the first stage of (s, a, h), (s, 11 Then Feva-Advantage will meet at most MH times the triggering condition for (5,a,h)
2. In the stage 1 (2 < < Ta(s,, a)) of (s, a, h), when (s, a) S (1- (1-+)100 - a) for round k, have (s, 9 (6.0)) (a.))))
Assume this case, meets times the corresponding triggering condition at the round k1 < k2 < ... < kp. For any i [p), since k; 2 k;- + 1, and k; and k are in the same stage, we have h ski1+1 < kkk Especially, we know n k < akpp < (1 + 1 (s. a). For any [p). since the triggering condition is met at the round k,, the increase of the
55

---

Published as a conference paper at ICLR 2025
visits to (s,a, (t) in round Ky is at least of (s, a). Therefore, according Equation 66.
have:
n c (s, Uh 1-1
(s, n (8,
ki+1
hh
M
Let So 0 and S
+1+1, then for i E [p] we have:
M
y/ (s.aa
M ki
+ y/ (s, a)
S.2
M R
M
M
M
M - 1
1/ (s.
M S +
M
From the inequality, with mathematical induction, can derive that:
5: 2 1 - M -
M ))) Vh
(s,a).
According to Sp-1 S 51 1 -y1111 - we know p S
log(H) logí ar-1)
+ 1. The last inequality
H
also holds for M- = 1.
For M = 1, we have 0.
3. In the stage t (2 < t [s, a)) of (s. h), when (s, (1 - - a) for round k, we have (x, a) n (s a)] Lxt v/h (s.a)].
Assume it meets q times the triggering condition for (s,a, a, h) in this case. For t 2 2, there exists positive integer such that r H < (s, a) < (r+1)MM) H and then (s, a) r. When the triggering condition of (s, a, h)) is met for one time, the increase in the visits is at least r. After it is met for q 1 times, we have r(g 1) S 2 yh (s, a) 2(r + M). Here, the first inequality is because wi./i
////// f-1 I 1 + 2/ H, and the second one is because y/ 1-1 (s, a) < (r + H. Therefore, we know q 1 4M + 1.
Combining the three cases, the total times of triggering conditions met for given triple (s, ht) is at most:
log H
MH
+ 4M +2
(T) 1).
log( M-
Therefore, combined with the inequality Equation (102)
we have:
log( H) log(( M-1
K Σ MH+ +
+4M +
(T)(s,a)-1) 1)
log(H)
log( MSAHS + 1)
< MSAH + SAH
+ 4M +2
M log(
log(1 +
M-11
log H
T log( SAHS + 1)
2 + SAH
+ 4M +
MM log( M-1
log(1 #
T
+ +1)
< M + 4MSAH (log (H) +3) log
SAH3
The last equality is because T MT and log(1 + + 2 x/2 for any 0 < x S The last inequality also holds for M = 1.
For Mayn FALSE, in each round, all M agents meet the trigger condition, then the round number
is at least:
T
K < SAH + 45AH² (log( H) + 3) log
SAHH + +1)
56


Reviews:
[{"review_id": "zUbkDxZQqT", "reviewer": "Reviewer_CkE8", "summary": "The paper addresses the problem of federated reinforcement learning (RL) in a model-free, tabular episodic Markov Decision Process setting.  The FedQ-Advantage algorithm  proposed allows multiple agents to collaboratively learn an optimal policy through a central server without sharing raw data. Variance reduction is achieved through a reference adaptive decomposition. Novel contributions include event triggered communication and policy switching. The result is an an algorithm with almost optimal cost and communication that scales logarithmically with $T$ and a constant that scales better than previous algorithms reported in the literature.", "questions": "Can the authors find a way to describe their work and provide some intuition behind the various steps. While I believe the validity of the results, I don't understand where the insights and intuition come from.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper seems technically sound, I only skimmed most of the material in the appendix but the structure of the proofs and flow makes sense. I believe the paper will be of interest to the ICLR community. I believe the combination of the reduced communication burden and the near optimal regret together make this a significant result.", "weaknesses": "The main weakness of the paper is that it is extremely notationally heavy and very little intuition is provided in any of the steps - a representative example of this is the section \"Updates of estimated value functions and policies\". It's 90% equation. I appreciate that it is difficult to keep this under control, but I believe this needs to be improved in order for it to have any value.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "yk5yn3Oyem", "reviewer": "Reviewer_d5vs", "summary": "This paper introduces FedQ-Advantage, a federated Q-learning algorithm for tabular episodic Markov Decision Processes. The algorithm utilizes reference-advantage decomposition to reduce variance and incorporates innovations like event-triggered communication, policy switching, and heterogeneous communication conditions. The paper proves that FedQ-Advantage achieves near-optimal regret with logarithmic communication cost.", "questions": "1. How does the event-triggered communication strategy affect the algorithm’s performance when applied to environments with highly variable agent performance?\n   \n2. What are the trade-offs between forced synchronization and the other two mechanisms (communication triggering and policy switching)?\n\n3. How would the FedQ-Advantage algorithm perform when applied to non-tabular environments or environments with larger state-action spaces, where Q-learning is typically more challenging?\n\n4. In figure 1, what do $k_{12}$ and $k_{22}$ mean? Are these typos? Moreover, can you explain again about the condition and process when communication occurs?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper presents a well-structured and coherent methodology, detailing the innovations introduced in FedQ-Advantage, such as reference-advantage decomposition and communication mechanisms.\n   \n2. The proof of the algorithm’s near-optimal regret and logarithmic communication cost is rigorous and well-supported. The mathematical treatment is thorough, providing strong theoretical guarantees for the algorithm’s performance.\n\n3. The algorithm's design, especially the heterogeneous communication triggering conditions and forced synchronization, shows creativity in addressing the challenges of federated learning.", "weaknesses": "1. The paper assumes a specific structure for communication conditions (e.g., event-triggered communication), which may not be universally applicable. The impact of these assumptions on algorithm performance in heterogeneous environments could be better analyzed.\n\n2. The description of forced synchronization and its impact on performance, while novel, lacks a detailed explanation of how it interacts with other parts of the algorithm. A clearer explanation would help in understanding its necessity and effectiveness in the overall approach.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "r53rr1HEMC", "reviewer": "Reviewer_bZxN", "summary": "This paper proposes a model-free federated reinforcement learning method called FedQ-Advantage. It focuses on  improving regret bounds and communication efficiency in multi-agent learning scenarios. This method leverages reference-advantage decomposition to reduce variance, designs an event-triggered communication method, and allows heterogeneous conditions. FedQ-Advantage achieves almost optimal regret, low communication cost, and near-linear regret speedup compared to the single-agent setting. It is especially efficient for distributed reinforcement learning tasks.", "questions": "1. Comparison with model-based approaches. How does FedQ-Advantage compare to model-based FedRL methods in terms of convergence speed and communication complexity, given that model-based methods often have lower complexity?\n2. Is there a trade-off between regret and communication complexity?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. SOTA Results. The proposed model-free FedRL method achieves a logarithmic communication cost.\n2. Novel techniques. The heterogeneous event-triggered communication in FedRL is new and effective.\n3. The guarantees are given with solid theoretical proof.", "weaknesses": "1. The tabular setting is studied without function approximation. The action and state space are discrete and finite.\n2. Literature Review. Is it possible to list federated value-based, and federated policy gradient-based methods separately and clearly? It would be better to have some pros and cons of federated Q-learning (value-based) methods compared to policy gradient-based methods.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "9HckQqW7xB", "reviewer": "Reviewer_RUvj", "summary": "This paper studies online federated Q-learning, which seeks to develop an optimal Q-function by utilizing collaborative exploration of multiple agents in a federated manner. The authors introduce a federated Q-learning algorithm that incorporates reference-advantage decomposition to reduce variance, which leads to the improved regret bound. Additionally, they propose event-triggered communication and policy switching, which save communication costs.", "questions": "See weaknesses.", "limitations": "", "rating": 3, "confidence": 4, "soundness": 3, "presentation": 1, "contribution": 2, "strengths": "1. The paper incorporated the variance reduction technique to federated Q-learning and demonstrated improved sample efficiency through regret analysis.\n2. They empirically demonstrated the performance of the proposed algorithm in a synthetic environment, comparing it with baseline algorithms.", "weaknesses": "1. Considering the existing literature on federated Q-learning [1,2,3], Q-learning with variance reduction (reference-advantage decomposition) [4,5], and Q-learning with unaligned stage design [5], the integration of these existing techniques into federated Q-learning seems incremental.\n2. The communication cost provided in this paper (O(SAH^2) or O(MSAH^2)) does not seem particularly low or noteworthy, given that other federated Q-learning algorithms [2,3] have demonstrated that O(H) communication rounds are sufficient. \n3. The presentation of the paper seems to need further refinement. Due to excessive notation and the use of vaguely defined terms, the descriptions of the algorithm and the equations are somewhat confusing, making them difficult to follow.\n4. In federated settings, privacy is very crucial; however, the algorithm seems to require the agents to send too many estimates to the server alongside value estimates, which could potentially expose too much information about the datasets.\n\n[1] Zhong Zheng, Fengyu Gao, Lingzhou Xue, and Jing Yang. Federated q-learning: Linear regret speedup with low communication cost. In The Twelfth International Conference on Learning Representations, 2024.\\\n[2] Jiin Woo, Laixi Shi, Gauri Joshi, and Yuejie Chi. Federated offline reinforcement learning: Collaborative single-policy coverage suffices. In International Conference on Machine Learning, 2024.\\\n[3] Sudeep Salgia and Yuejie Chi. The sample-communication complexity trade-off in federated Q-learning. arXiv preprint arXiv:2408.16981, 2024.\\\n[4] Gen Li, Laixi Shi, Yuxin Chen, Yuantao Gu, and Yuejie Chi. Breaking the sample complexity barrier to regret-optimal model-free reinforcement learning. Advances in Neural Information Processing Systems, 34:17762–17776, 2021.\\\n[5] Zihan Zhang, Yuan Zhou, and Xiangyang Ji. Almost optimal model-free reinforcement learning via reference-advantage decomposition. Advances in Neural Information Processing Systems, 33: 15198–15207, 2020.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "mzsr6faaM5", "reviewer": "Reviewer_wG6t", "summary": "This paper proposes the first model-free federated tabular RL algorithm that achieves almost optimal regret with logarithmic communication cost. The authors adopt a reference-advantage decomposition when updating the $Q$ function via UCB for variance reduction. In addition, several designs surrounding communication and synchronization ensure a lower communication cost. Numerical experiments also support the benefit of FedQ-Advantage.", "questions": "* The setting requires more description. I am not sure if I misunderstood the algorithm design, but it seems that the notation and Figure 1 is not clear to me. Specifically, $k^t_h(s,a)$ is denoted as the index of the first round that belongs to stage t, so I thought \"t\" refers to the index of stage while the first row in Figure indicates $k_2^1$ belongs to stage 2. In addition, the second row in Figure 1 shows $k_{12}$ and $k_{22}$ also confuses me. Please also explain more about the logic of stage $t$ how it is composed of rounds $k_h^t, k_h^t +1, ..., k_h^{t+1}-1$.\n\n* Can you mainly compare your threshold/ event-triggered communication strategy with [1, 2]? Again, I know that your work is in a tabular setting, but since I am not fully clear with Figure 1. A comparison can make your design more readable. \n\n* I was wondering how your method can be extended to function approximation out of a tabular setting with the curse of dimensionality, especially for those main components in your algorithm, such as separate event-triggered communication and policy switching, heterogeneous communication triggering conditions, optional forced synchronization, and reference-advantage decomposition. Any challenge or limitation for your designs to convert to linear functional approximation setting?\n\n* In Figure 3, it shows that the empirical regret from Concurrent UCB-Advantage is larger than FedQ-Advantage while Concurrent UCB-Advantage has the same regret as FedQ-Advantage from a theoretical standpoint. Could you please elaborate more on where the gap comes from? I am also interested in the rounds of communication as the comparison for Figure 3 (FedQ-Advantage vs. Concurrent UCB-Advantage), which you can ignore UCB-A: $10^6$.\n\n#### [1] Dubey, Abhimanyu, and Alex Pentland. \"Provably efficient cooperative multi-agent reinforcement learning with function approximation.\" arXiv preprint arXiv:2103.04972 (2021).\n\n#### [2] Min, Yifei, et al. \"Cooperative multi-agent reinforcement learning: Asynchronous communication and linear function approximation.\" ICML, 2023", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "* The authors effectively highlight the contributions, including technical novelty.\n* FedQ-Advantage is the first design for an almost optimal federated model-free RL algorithm that enjoys a logarithmic communication cost in a federated tabular setting.\n* Theoretical analysis is provided and it can match the performance of the state-of-the-art results in tabular RL.", "weaknesses": "* The related work is not comprehensive. The authors mentioned *most existing model-free federated algorithms do not actively update the exploration policies for local agents and fail to provide low regret*, which is not precise. Please also consider including [1, 2, 3] for full comparison. Although they are more based on functional approximation instead of pure tabular setting, they definitely incorporate active exploration strategies in federated learning.\n* The writing can be improved, especially the algorithm design section. Please refer to the questions below.\n\n\n#### [1] Dubey, Abhimanyu, and Alex Pentland. \"Provably efficient cooperative multi-agent reinforcement learning with function approximation.\" arXiv preprint arXiv:2103.04972 (2021).\n\n#### [2] Min, Yifei, et al. \"Cooperative multi-agent reinforcement learning: Asynchronous communication and linear function approximation.\" ICML, 2023\n\n#### [3] Hsu, Hao-Lun, et al. \"Randomized Exploration in Cooperative Multi-Agent Reinforcement Learning.\" NeurIPS, 2024", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "3w8wCt3Z0b", "reviewer": "Reviewer_7yMZ", "summary": "The paper presents FedQ-Advantage, a novel model-free federated reinforcement learning (FRL) algorithm designed for tabular episodic Markov decision processes (MDPs). This algorithm addresses the challenges of achieving optimal learning performance with minimal communication costs in a distributed setting where multiple agents collaborate under the coordination of a central server.\nThe proposed FedQ-Advantage enhances existing federated Q-learning methods by introducing mechanisms for variance reduction through reference-advantage decomposition and active policy updates coordinated by the central server.\nThe algorithm employs event-triggered communication, aligning communication rounds with specific conditions while allowing unaligned updates across state-action-step tuples. This approach reduces communication overhead significantly.\nThe introduction of heterogeneous triggering conditions allows agents to optimize exploration early in the learning process, further enhancing efficiency by limiting unnecessary communication later on.\nAn optional forced synchronization mechanism improves robustness and reduces waiting times for agents, streamlining the overall learning process.\nThe paper demonstrates that FedQ-Advantage achieves an almost optimal regret that approaches the information theoretical bound, scaling logarithmically with the number of communication rounds, and provides near-linear regret speedup compared to single-agent algorithms.\nThe authors propose heterogeneous triggering conditions that decrease the synchronization frequency, ultimately improving communication costs.\nOverall, the paper makes significant strides in federated reinforcement learning by successfully developing an algorithm that balances optimal learning performance with low communication costs. Statistical theory demonstrates that FedQ-Advantage is the first model-free federated RL algorithm to achieve both almost optimal regret and logarithmic communication efficiency. These contributions position this paper as a valuable contribution to the field.", "questions": "Please see the **Weaknesses** section.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "This paper is theoretically solid and well structured. \n\nNovelty: This paper develops the first near-optimal model-free RL algorithm under the setting of a tabular MDP and a communication graph with a central server. \n\nSignificance: The communication cost matches with the best policy switching cost in Q-learning. \n\nQuality: The paper has good quality. The theoretical results look solid. It is good to see the synthetic experimental results match the theory. .  \n\nOverall, I think this is a good theoretical paper.", "weaknesses": "There is no major flaw in this paper. However, the following can be addressed.\n\n1. The paper is not easy to read and can be improved. For examples:\n\na) At the end of page 5, the paper mentioned that the visitation number $y_{t+1}$ is similar to the exponential rate in related works due to the first case and ‘Equation 4’. However, equation 4 is in page 7 and thus it is very hard to really understand what it means when reading the sentence Page 5. To improve, I think the authors could (i) either not to add such kind of details in section 3.1. Just presenting some intuition would be enough, or (ii) provide a brief preview of the key idea from Equation 4 when it's first mentioned on page 5. These might help readers follow the logic more easily without having to jump ahead in the paper.\n\nb) Page 7, Item 4 can be improved. It is very hard to read. I understand that it is inevitable for this paper to be notationally heavy. But in the main text one might still want to avoid in-line equations of such lengths. If indeed one wish to insert these in the main text, then I think an explanation after each chunk of equations is necessary. The explanation can be as short as one sentence like “the central server finds the tuples whose visitation number exceeds… ”.\n\n2. The claimed technical novelty of “non-martingale concentration” is a bit misleading. If my understanding is correct, the paper is simply approximating a non-martingale sequence with a martingale. In order to achieve this, the algorithm is specifically designed with a heterogeneous trigger condition that forces communication with the server when the number of visitations exceeds a threshold. This will ensure the ‘distance’ between the non-martingale sequence and the implicit martingale sequence to be small enough. After that, the entire error bound is a standard martingale convergence argument. If my understanding is not wrong, then this seems to me a quite straightforward approach to handle concentration under an asynchronous communication setting. I wouldn't expect the paper to give a real non-martingale concentration inequality. After all, if the communication is truly arbitrary and random, then I imagine it is impossible to get any valid concentration result.\nTo resolve this issue, I would suggest not to call this a ‘non-martingale’ concentration to avoid misunderstanding from people doing literature search for real non-martingale concentration. \n\nOverall, I do not detect major technical issues in this theoretical paper. The above issues should be easily fixable.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)