Asynchronous Multi-Agent Reinforcement Learning with General Function Approximation

Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 20:31:43

Abstract: We study multi-agent reinforcement learning (RL) where agents cooperate through asynchronous communications with a central server to learn a shared environment. Our first focus is on the case of multi-agent contextual bandits with general function approximation, for which we introduce the Async-NLin-UCB algorithm. This algorithm is proven to achieve a regret of $\tilde{O} (\sqrt{T \dim_E(\mathcal{F}) \log N(\mathcal{F})})$ and a communication complexity of $\tilde{O} (M^2 \dim_E(\mathcal{F}))$, where $M$ is the total number of agents and $T$ is the number of rounds, while $\dim_E(\mathcal{F})$ and $N(\mathcal{F})$ are  the Eluder dimension and the covering number of function space $\mathcal{F}$ respectively. We then progress to the more intricate framework of multi-agent RL with general function approximation, and present the Async-NLSVI-UCB algorithm. This algorithm enjoys a regret of $\tilde{O} (H^2 \sqrt{K \dim_E(\mathcal{F}) \log N(\mathcal{F})})$ and a communication complexity of $\tilde{O} (H M^2 \dim_E(\mathcal{F}))$, where $H$ is the horizon length and $K$ the number of episodes. Our findings showcase the provable efficiency of both algorithms in fostering collaborative learning within nonlinear environments, and they achieve this with minimal communication overhead.

Main paper: 
 introduction: 
 Multi-agent reinforcement learning (RL) is an important paradigm in RL, and has been successfully applied to real-world tasks such as robotics [Williams et al., 2016 , Liu et al., 2019 , Ding et al., 2020 , Liu et al., 2020 , Na et al., 2022] , games [Vinyals et al., 2017 , Berner et al., 2019 , Jaderberg et al., 2019 , Ye et al., 2020] , and control systems [Bazzan, 2009 , Yu et al., 2014 , 2020 , Min et al., 2022 , Xu et al., 2023] . By learning cooperatively, agents benefit from sharing learning experiences, enabling them to collectively enhance their decision-making capabilities. This collaborative process is usually accomplished through the utilization of a central server, whose task is to aggregate local data and deliver feedback for the agents.There has been an excellent line of work establishing provably efficient algorithms for multi-agent bandits and RL. However, most existing works are restricted to the synchronous setting, where communications between all agents and the server must happen simultaneously. This is impractical since in many scenarios the availability of agents may vary and be unpredictable. Ideally, communication should be allowed to happen asynchronously to offer the agents more flexibility. He et al. [2022] and Min et al. [2023] studied this setting respectively for linear contextual bandits and linear Markov Decision Processes (MDPs), both of which assumes linearity in the environment, and introduced algorithms with low regret and communication cost. Yet the linear function class is quite limited, and does not encompass practical reinforcement learning scenarios where nonlinearity is prevalent.To address the aforementioned drawback, in this work, we tackle environments with general function approximation, broadening the applicability of the algorithm to more realistic and complex scenarios.We first delve into multi-agent contextual bandits with general function approximation, where multiple agents interact with homogeneous environments in parallel to solve a common objective. Notably, the communication protocol is designed to be flexible and asynchronous, allowing agents to initiate communication with the server and acquire new policy functions whenever the need arises. The primary objective is to minimize total regret while reducing communication cost as much as possible.Submitted to 38th Conference on Neural Information Processing Systems (NeurIPS 2024). Do not distribute.We propose an algorithm Async-NLin-UCB, which adapts a fully asynchronous communication protocol, and leverages various methods for tackling nonlinear function approximation. Despite the flexibility of communication, our algorithm performs almost as well as a single agent, in terms of a regret that is mostly independent of the number of agents and a low communication cost.We then progress to multi-agent RL with general function approximation under similar requirements and objectives. We propose an algorithm named Async-NLSVI-UCB based on Least-Squares Value Iteration (LSVI) to learn the underlying Markov decision processes (MDPs), which demonstrates similar advantages with provably low regret and communication cost.Our main contributions are summarized in the following:• For asynchronous multi-agent nonlinear contextual bandits, we propose the algorithm Async-NLin-UCB, which enjoys an O( T dim E (F) log N (F) + dim E (F)) regret and an O(M 2 dim E (F)) communication complexity, where dim E (F) and N (F) are respectively the Eluder dimension and the covering number of function space F.• For asynchronous multi-agent nonlinear MDPs, we propose the algorithm Async-NLSVI-UCB, which enjoys an O(H 2 K dim E (F) log N (F) + H 2 dim E (F)) regret and a communication complexity of O(HM 2 dim E (F)).• At the core of our algorithm, we design a communication criterion in order to tackles the challenges posed by both asynchronous communication and the nonlinearity of function approximation. To guarantee a low communication cost, we propose a low switching communication criterion that allows the agent to trigger communication rounds.• We carefully design our download content from server to local agents, which consist only of decision and bonus functions, with no mention of any specific historical data. This effectively protects user data against exposure by disallowing local users from obtaining the data of others.Notation. We use lower case letters to denote scalars. We denote by [n] the set {1, . . . , n}. For two positive sequences {a n } and {b n } with n = 1, 2, . . . , we write a n = O(b n ) if there exists an absolute constant C > 0 such that a n ≤ Cb n holds for all n ≥ 1. We use O(•) to further hide the polylogarithmic factors. For two non-negative integers a, b satisfying a < b and a sequence {s i } indexed by integers i, we use s 2 Related WorkQuestion: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?Answer: [Yes] Justification: We accurately summarize our contribution and main results in the abstract, and elaborate further on motivation and main techniques in our introduction.Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper.• The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.• The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.• It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
multi-agent bandits: 
 First, there is a multitude of previous work on distributed or federated multi-armed bandits and stochastic linear bandits [Liu and Zhao, 2010 , Szorenyi et al., 2013 , Landgren et al., 2016 , Chakraborty et al., 2017 , Landgren et al., 2018 , Martínez-Rubio et al., 2019 , Sankararaman et al., 2019 , Wang et al., 2020a ,c, Zhu et al., 2021 , Huang et al., 2021] . For the more realistic setting of contextual bandits, most previous work are within the scope of linear contextual bandits with synchronized communication. Korda et al. [2016] introduced two novel distributed confidence ball (DCB) algorithms for linear bandit problems in peer-to-peer networks. Wang et al. [2020c] considered both P2P and star-shaped communication, achieving near-optimal regret and low communication cost that is largely independent of the time horizon in their algorithm DisLinUCB. Dubey and Pentland [2020] proposed FedUCB, an algorithm focusing on differential-privacy. Li and Wang [2022] first considered an asynchronous communication protocol and proposed the algorithm Async-LinUCB with near-optimal regret, yet the algorithm contains a download step for all agents triggered by the central server. Their results are flexible and contains a parameter to control the trade-off between regret and communication cost. He et al. [2022] improved the setting to a fully asynchronous communication, proposing the algorithm FedLinUCB with near-optimal regret of O(d √ T ) and low communication cost of O(dm 2 ), comparable to the benchmark in singleagent contextual linear bandits [Abbasi-Yadkori et al., 2011] . We consider the same communication protocol in our results. A summary of these results along with ours can be found in the first four rows of Table 1 .Multi-agent reinforcement learning is decidedly more challenging than contextual bandits. There is also a vast literature on this setting, with many works discussing different aspects of multi-agent RL Algorithm Regret Communication Fully asynchrnous DisLinUCB d √ M T log 2 T d 3 M 3/2 ✘ [Wang et al., 2020c] Async-LinUCB dM (1-γ)/2 √ T log T dM 1+γ log T ✘ [Li and Wang, 2022] FedLinUCB d √ T log T dM 2 log T ✓ [He et al., 2022] Async-NLin-UCB√ dim E log N T log T dim E M 2 log 2 T ✓ (ours)Coop-LSVI d 3/2 H 2 √ M K log K dHM 3 ✘ [Dubey and Pentland, 2021] Async-Coop-LSVI-UCB d 3/2 H 2 √ K log K dHM 2 log K ✓ [Min et al., 2023] Async-NLSVI-UCB√ dim E log N H 2 √ K log K dim E HM 2 log 2 K ✓ (ours)Table 1 : Comparison of our result against baseline methods for multi-agent contextual bandits and MDPs. Note that the first four rows are for contextual bandits, and the last three are for reinforcement learning. Only our algorithms are in the general function approximation setting. We abbreviate dim E = dim E (F) and N = N (F), and hide logarithmic factors. For algorithms with synchronized communication, each communication round actually corresponds to M rounds in asynchronous settings, which explains the extra M terms. than ours. For example, there are works focusing on convergence guarantees [Zhang et al., 2018b ,a, Wai et al., 2018] , non-stationary or heterogeneous environments [Lowe et al., 2017 , Yu et al., 2021 , Dubey and Pentland, 2021 , Kuba et al., 2022 , Liu et al., 2022 , Jin et al., 2022] , and deep federated RL [Clemente et al., 2017 , Espeholt et al., 2018 , Horgan et al., 2018 , Nair et al., 2015 , Zhuo et al., 2019] ,to name a few. We refer to a recent survey on federated reinforcement learning Qi et al. [2021] for a more comprehensive summary.Narrowing it down to multi-agent RL with function approximation, the benchmark is the LSVI-UCB algorithm in the single-agent setting [Jin et al., 2020] , with an O(d 3/2 H 2 √ K) regret. Dubey and Pentland [2021] proposed CoopLSVI for multi-agent linear MDPs, which requires a synchronized communication through central server, and proves a regret of O(d 3/2 H 2 √ M K). They also extended their result to the heterogeneous setting. Min et al. [2023] considered the fully asynchronous setting and introduced the Async-Coop-LSVI-UCB algorithm, with a O(d 3/2 H 2 √ K) regret not dependent on the number of agents M , as well as a low communication cost. A summary of these results along with ours can be found in the last three rows of Table 1 .Reinforcement learning with general function approximation extends the well-studied case of linear MDPs to more general classes of MDPs, and has gained a lot of traction in recent years [Wang et al., 2020b , Jin et al., 2021 , Foster et al., 2023 , Du et al., 2021 , Agarwal and Zhang, 2022 , Agarwal et al., 2023] . Previous works focus on different measures of complexity for the function classes, for example the Bellman rank proposed by Jiang et al. [2017] , the Bellman Eluder dimension introduced in Jin et al. [2021] , the Decision-Estimation Coefficient in Foster et al. [2023] , and generalized Eluder dimension in Agarwal et al. [2023] . Our work considers the Eluder dimension with the introduction of uncertainty estimators D 2 , which has been widely utilized to establish results in RL with general function approximation [Agarwal et al., 2023 , Zhao et al., 2023 , Ye et al., 2023 , Di et al., 2023] .Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes]Justification: All assumptions made for our theoretical analysis are present and stated clearly within the main paragraphs of our paper. Discussions on the applicability of these assumptions are also included.Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.• The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.• The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.• The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.• The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.• If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.• While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
preliminaries: 
 In this section, we introduce the formal definition of both multi-agent nonlinear contextual bandits and MDPs and some related concepts, and discuss the asynchronous communication protocol.We assume a global action set A that is known to all agents. At each round t ∈ [T ], a single arbitrary agent m t ∈ [M ] is chosen to participate. The agent receives a contextual decision set A t ⊆ A and chooses from the set an action a t ∈ A t to perform, and subsequently receives a random reward r t .The assumption of general function approximation is that the reward is generated according toEQUATIONwhere f * is the ground truth objective function, and η t is a random noise variable. We assume the the objective function lies within a known function class F. In addition, we also make the following assumptions regarding the function class and noise variables, which are standard assumptions for contextual bandits [Abbasi-Yadkori et al., 2011 , He et al., 2022] :Assumption 3.1. Suppose the following conditions hold for the contextual bandits environment:• For any f ∈ F and a ∈ A, |f (a)| ≤ 1;• η t is R-sub-Gaussian conditioned on data history: E e ληt a 1:t , m 1:t , r 1:t-1 ≤ exp(R 2 λ 2 /2), ∀λ.Learning Objective. The primary goal of contextual bandits is to minimize the cumulative regretReg(T ) = T t=1 [f * (a t ) -max a∈At f * (a)].Notice that this summation is across all time steps does not depend on agent participation order, as should be the case for the resulting regret bound. To achieve this goal, agents are allowed to communicate with the server to upload their interaction history and update their policy. The secondary learning objective is to reduce communication overhead. We will explain the communication protocol further in Section 3.4.We consider episodic MDPs, which are a classic family of models in reinforcement learning [Sutton and Barto, 2018] . It is characterized by the following elements, which we assume to be homogeneous across all agents: a state space S, an action space A, the horizon length H, transition probabilityfunctions P = {P h (•|•, •)} H h=1 and reward functions {r h (•, •)} H h=1 ). Similar to the bandit case, for each episode k = 1, • • • , K, a single agent m = m k is chosen to participate. An episodek begins with an initial state s k 1 , which is drawn from an unknown fixed distribution. Then for steps h = 1, • • • , H, the participating agent m selects an action a k h based on the observed state s k h . After each action, the agent receives a reward r k h = r h (s k h , a k h ), where r h : S × A → R is the reward function at step h. Here for the sake of convenience, we assume the reward function to be deterministic, but it is not difficult to generalize our result to stochastic rewards. We also assume r h (s, a) ∈ [0, 1] for all (s, a) ∈ S × A without loss of generality. The environment then transitions to the next state according to s k h+1 ∼ P h (•|s k h , a k h ), where P h is the transition probability at step h.The episode terminates when r H is observed.The strategy an agent employs to interact with the environment is called the agent's policy, which can be described by a set of decision functions π = {π h } H h=1 , where π h : S → A is the decision function at level h, mapping the current state to an action to select.Value Functions. For any policy π = {π h }, we define Q-value functions and V -value functions:EQUATIONwhere the expectation is taken over the trajectory (s 1 , a 1 , • • • , s h , a h ), determined by the transition probability functions P and policy π. The optimal strategy π * is the maximizer of the value functions:EQUATIONFunction Approximation. We approximate Q-value functions with function classes {F h } H h=1 , which contain real value functions with domain S × A. One basic assumption is that Q * h ∈ F h for all steps h ∈ [H]. Now with the convention that functions at level H + 1 are uniformly zero, i.e., f H+1 = 0, we define the Bellman operator T h :(T h f h+1 )(s h , a h ) := E r h (s h , a h ) + f h+1 (s h+1 ) s h , a h ,and we expect T h to map any function in F h+1 to a function in F h , i.e., T h F h+1 ⊆ F h . This is called the completeness assumption, which is a fundamental assumption in RL with general function approximation [Wang et al., 2020b , Jin et al., 2021] .Learning Objective. The primary goal in multi-agent MDPs is to minimize the cumulative regret over K episodes Reg(K) = K k=1 V * 1 (s k 1 ) -V π m,k 1 (s k 1 ), where π m,k is the policy of agent m = m k at round k, while the secondary objective is to minimize the communication cost.To measure the complexity of the learning objective, Russo and Van Roy [2013] first proposed the concept of Eluder dimension, which we define below. Definition 3.2 (ϵ-dependence). For a function classF on domain D, a point z ∈ D is ϵ-dependent on Z ⊆ D if, for any f 1 , f 2 ∈ F satisfying z ′ ∈Z f 1 (z ′ ) -f 2 (z ′ ) 2 ≤ ϵ, it must hold that |f 1 (z) -f 2 (z)| ≤ ϵ. Accordingly, z is ϵ-independent of Z if it is not ϵ-dependent on Z.Definition 3.3 (Eluder dimension). The ϵ-Eluder dimension dim E (F, ϵ) is the length of the longest sequence of elements in D satisfying that, for some ϵ 0 > ϵ, each element is ϵ 0 -independent of the set consisting of its predecessors.It has been demonstrated that the Eluder dimension roughly corresponds to regular dimension concepts in linear and quadratic cases [Russo and Van Roy, 2013] , and that the Eluder family is strictly larger than the generalized linear class [Li et al., 2022] . Note that our Eluder definition can be applied to either the contextual bandit case with D = A or the MDPs case with D = S × A.We also introduce covering number for function classes [Wainwright, 2019] in the following:Definition 3.4 (Covering number). An ϵ-cover of F is any subset F ϵ ⊆ F such that for any f ∈ F,there exists f ′ ∈ F ϵ that ∥f -f ′ ∥ ∞ ≤ ϵ.The covering number of F, denoted by N (F, ϵ), is the minimal cardinality of its ϵ-cover.We consider a star-shaped communication model [He et al., 2022 , Min et al., 2023] , where the agents communicate through a central server to collaborate. To ensure asynchronous communication, we mandate that all communications must be initiated by a participating agent. Specifically, at the end of a time step / episode, the agent will decide whether or not to trigger a communication round. If so, the agent uploads its local data history and receives some global data for future decision making. The communication cost is the total number of communication rounds initiated by the agents.One variability is the form of global data that the communicating agent downloads from server. It may be tempting to have the server send all its stored trajectories to the agent for future decision making, but this will unnecessarily expose other agents' data to the current participating agent. We will come back to this issue and our solution in Section 4.2.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?Answer: [NA] Justification: Our theoretical paper does not present any experimental results.Guidelines:• The answer NA means that paper does not include experiments requiring code.• Please see the NeurIPS code and data submission guidelines (https://nips.cc/ public/guides/CodeSubmissionPolicy) for more details.• While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).• The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https://nips.cc/public/guides/CodeSubmissionPolicy) for more details.• The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.• The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only a subset of experiments are reproducible, they should state which ones are omitted from the script and why.• At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).• Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
multi-agent contextual bandits: 
 In this section, we introduce the Asynchronous Nonlinear UCB (Async-NLin-UCB) algorithm designed for multi-agent contextual bandits with general function approximation, and provide a theoretical result for its regret and communication cost.Algorithm 1 takes as input the total number of time steps T , regularization parameter λ, communication parameter α and exploration radii {β t } T t=1 .In the algorithm, there are some variables that go through different versions as t progresses through Send new data Z loc m to server.10:on server:11:Update Z ser = Z ser ∪ Z loc m .12:Calculate f according to (5) and the bonus function b = B A (Z ser , F; λ, β t ).13:Send f + b and b to agent m.14:end of server 15:Agent m receives decision and bonus functionsf m = f + b, b m = b, then set Z loc m = ∅.16:end if 17: end for After exploration, the agent checks if the switch condition is true using its bonus function:EQUATIONwhere t ′ is the last time step when agent m communicated with the server. If so, the agent initiates a communication round and uploads its local data (Line 9), prompting the server to begin global policy updates. We will discuss the reasons behind this switch condition in Section 4.2.Part II: Server Updates. After receiving a new local data history from an agent, the server merges the data into its global dataset Z ser t (Line 11), and calculate a function f t+1 ∈ F which minimizes the sum of squares error according to the current dataset Z ser t (Line 12):f t+1 = argmin f ∈F (a,r)∈Z ser t f (a) -r 2 .(5)The next step is to obtain a bonus function b t+1 from the oracle B A from Definition 4.1 (Line ??).We discuss the specifics of this construction in detail up next in Section 4.2. Finally, the server sends the optimistic value function f t+1 + b t+1 and the bonus function b t+1 back to agent m for future exploration and updates; agent m also resets its local data history to an empty set (Lines 13 and 15).In this section, we introduce uncertainty estimators and bonus functions, and give a detailed explanation for our communication criterion (4). Most of these apply to the MDPs setting as well.Uncertainty Estimators. First we define the uncertainty estimator of new data a against data history Z, which is considered in many works on bandits and RL with general function approximation [Gentile et al., 2022 , Agarwal et al., 2023] :EQUATION)here λ is the regularization parameter, F is a function class. Intuitively, the uncertainty estimator measures the difference between functions on new data a against the difference on historical data Z. EQUATION)where we use Z new : D → R ≥0 satisfying for any z ∈ D that • b(z) ≥ max f 1 (z) -f 2 (z) : f 1 , f 2 ∈ F, (z,e)∈Z f 1 (z) -f 2 (z) 2 ≤ β 2 ; • D λ,F (z; Z) ≤ b(z)/ β 2 + λ ≤ C B D λ,F (z; Z),where C B is an absolute constant.Remark 4.2. Similar bonus function oracles have been proposed in previous works (Definition 3 in Agarwal et al. [2023] ). The accessibility of these oracles is also supported by previous works that proposed methods to compute bonus functions [Kong et al., 2023 , Wang et al., 2020b] . In this definition, we leave the domain and data format to be variable so the oracle can be applied to both contextual bandits and MDPs. For bandits, the domain is A, and the data format has z = a and e = r.The first property of the bonus function guarantees the optimism of decision functions f t+1 + b t+1(see Lemma 6.1 for MDPs or Lemma A.2 for bandits), while the second property links bonuses to uncertainty estimators.Switch Condition Based On Bonus Functions. If we try to adapt the switch condition (7) in our setting, a local agent will require access to historical data Z old t to calculate uncertainty estimatorsD 2 λ,F (a; Z old t ).For multi-agent learning, this dataset consists of the collective data from all agents, and giving local agent access is a clear violation of data privacy. Our solution is to let local agents download bonus functions and set communication criterion to (4), using bonus functions instead of uncertainty estimators.Decision Functions Based On Bonus Functions. Another benefit of introducing the bonus function is evident from our exploration method in line 6. A common practice for nonlinear RL algorithms is to construct confidence sets of functions during policy update, and find the optimal function within the confidence sets during exploration [Agarwal et al., 2023 , Ye et al., 2023] . However, in a multi-agent setting, this would involve the download of confidence sets, which is impractical due to the complex nature of function classes. With the bonus function, local agents need only download the decision function from the server for future exploration, which for contextual bandits is simply f t+1 + b t+1 .Our main results for Algorithm 1 are summarized in the following theorem, which provides a regret upper bound and communication complexity order.Theorem 4.3.By taking γ = O(1/T ), β t = C β,1 √ λ + RC(M, α) log(3M N (F, γ)/δ) and C(M, α) = √ 1 + M α √ 1 + M α + M √ α , the regret of Algorithm 1 within T rounds is O √ T β 1 (1 + M α) dim E log(T / min{1, λ}) + (1 + M α) dim E log 2 (T / min{1, λ}) ,where we abbreviate dim E := dim E (F, λ/T ); the total communication complexity is except for an extra 1 + M α term in the communication cost, an unimportant term when taking α = 1/M 2 that comes from the complication of communication cost analysis in nonlinear settings.O (1 + M α) 2 /α dim E log 2 (T / min{1, λ}) Remark 4. 
multi-agent reinforcement learning: 
 In this section, we introduce the Asynchronous Nonlinear Least Squares Value Iteration UCB (Async-NLin-UCB) algorithm for multi-agent MDPs with general function approximation, and a corresponding theoretical result.To better represent the elements in the datasets, we sometimes use o h to represent the tuple (s h , a h , r h , s h+1 ) and z h to represent (s h , a h ) when there is no confusion. Similar to the bandit case, we give some variables an extra subscript k here for clarity, which denotes the version of the variable before (not included) Line 14 at episode k.Algorithm 2 Federated Nonlinear MDPs 1: Input: total number of rounds K, parameters λ, α,β k,h for k = [K] and h ∈ [H] 2: Server init: Set Z ser h = ∅ for all h ∈ [H]. 3: Local init: ∀m ∈ [M ] and h ∈ [H], set Q m,h = 1, b m,h = B(∅, F h ; λ, β 0,h ), Z loc m,h = ∅. 4: for k = 1, . . . , K do 5: Agent m = m k ∈ [M ]is active and receives initial state s k 1 ∈ S.for h = 1, . . . , H do 7:Take actiona k h = argmax a∈A Q m,h (s k h , a), receive reward r k h and next state s k h+1 . 8: Update Z loc m,h = Z loc m,h ∪ {(s k h , a k h , r k h , s k h+1 )}. 9:end for 10:if switch condition ( 8) is met then 11:Send new data {Z loc m,h } h∈[H] to server.12:on server:13: Update Z ser h = Z ser h ∪ Z loc m,h .14:Initialize Q H+1 = V H+1 = 0.15:for h = H, H -1, • • • , 1 do 16:Calculate f h according to ( 9) and bonus function bh = B S×A (Z ser h , F h ; λ, β k,h).Calculate Q h and V h according to (11).18:end forSend {Q h } H h=1 and {b h } H h=1 to agent m.end of server 21: Agent m receives Q m,h = Q h , b m,h = b h and resets Z loc m,h = ∅ for all h ∈ [H].{(s k h , a k h , r k h , s k h+1 )} H h=1, which is then stored into the local historical datasets Z loc m,k,h (lines 6 -9).After exploration, the agent checks for the following switch condition: there exists h ∈ [H] so thatEQUATIONwhere k ′ is the last communication round for m. If so, the agent triggers communication (Line 11).Part II: Server Updates. After receiving new data, the server merges it with its global datasets Z ser k,h (Line 13) and calculates value function estimates {Q k+1,h } H h=1 and {V k+1,h } H h=1 using LSVI.Suppose we already have Qand V -value function estimates Q k+1,h+1 and V k+1,h+1 at level h + 1.We solve the least squares problem for f h to minimize the Bellman error (Line 16):EQUATION)We now also define the uncertainty estimator of a new pair of data z = (s, a) against data history Z with normalization parameter λ and function class F asD λ,F (z; Z) = sup f1,f2∈F |f 1 (z) -f 2 (z)| λ + o ′ ∈Z |f 1 (z ′ ) -f 2 (z ′ )| 2 .(10) Similar to the bandits setting, the uncertainty can be approximated with the bonus function acquired from an oracle B S×A in Definition 4.1. In this case, the domain D = S × A, and the data format corresponds to z = (s, a) and e = (r, s ′ ). Despite these definitions not depending on the step h, we expect the parameters z, Z, F to always come from same step h. Finally, we allow the bonus function classes W h = W h,S×A to vary between different levels.After calling oracle for b k+1,h (Line 16), we can obtain value function estimates (Line 17):Q k+1,h (s, a) = f k+1,h (s, a) + b k+1,h (s, a), V k+1,h (s) = sup a∈A Q k+1,h (s, a). (11) Iterating through h = H, • • • , 1, the server calculates a set of updated Q-value functions {Q k+1,h } Hh=1 and bonus functions {b k+1,h } H h=1 , and send them back to agent m for future exploration and updates (lines 19 and 21).We summarize the regret and communication cost of Algorithm 2 in the following theorem:Theorem 5.1. Taking γ = O(1/HK), β h,k = C β,2 √ λ + HC(M, α) log(3HM N (γ)/δ) and N (γ) := max h N (F h , γ)N (F h+1 , γ)N (W h+1 , γ), the regret within K rounds is bounded by O H β 2 (1 + M α) dim E K log(K/ min{1, λ}) + H 2 (1 + M α) dim E log 2 (K/ min{1, λ}) .where we abbreviate dim E := dim E (F, λ/K); the total communication complexity is O H(1 + M α) 2 α dim E (F, λ/K) log 2 (K/ min{1, λ}) . Remark 5.2. This result when reduced to linear MDPs correspond well to Theorem 5.1 in Min et al. [2023] .Taking α = 1/M 2 , we get a regret of O H 2 √ K dim E log N + H 2 dim E and a communication cost of O HM 2 dim E , where N = max h {N (F h , γ), N (W h , γ)}.6 Proof SketchIn this section, we provide an outline for the proof of Theorem 5.1, while a more detailed proof can be found in Appendix B, and the full versions of the following lemmas are in Appendix B.1. 
regret upper bound: 
 For the regret upper bound, the first lemma establishes optimism of value function estimates.Lemma 6.1. Taking β k,h as in Theorem 5.1, with probability at least 1 -δ, for all k, z ∈ S × A andh ∈ [H], |T h Q k+1,h+1 (z) -f k+1,h (z)| ≤ b k+1,h (z).This allows us to decompose regret into a sum of bonuses:Reg(K) = K k=1 V * 1 (s k 1 ) -V π m,k 1 (s k 1 ) ≤ K k=1 H h=1 E π m,k Q m,k,h -T h Q m,k,h+1 (s k h , a k h ) ≤ K k=1 H h=1 2b m,k,h (s k h , a k h ). (12)The sum of bonuses is equal to the sum of uncertainty up to a constant, which we bound in the following lemma corresponding to the elliptical potential lemma [Abbasi-Yadkori et al., 2011] . Lemma 6.2. Define universal datasets asZ all k,h = {o k ′ h } k ′ ∈[k]. Then we have for any h ∈ [H]: K k=1 D 2 λ,F (z k h ; Z all k-1,h ) = O dim E (F, λ/K) log 2 (K/ min{1,Lemma 6.3. For any z ∈ S × A, k ∈ [K], h ∈ [H], D 2 λ,F (z; Z ser k,h ) ≤ (1 + M α)D 2 λ,F (z; Z all k,h ).With these, we can deduce the regret bound from (12).For communication cost, we employ an epoch segmentation scheme, which defines N epochs segmented by episodes {k i } N i=1 , with k i being the smallest episode satisfyingEQUATION)This is a generalization of epoch segmentation based on doubling determinants in linear settings, yet the lack of determinant in the nonlinear case dramatically increases its complexity. Intuitively, switch condition (8) suggests an agent must gather a substantial amount of data to trigger communication, yet a careful analysis according to (13) yields a maximum of M + C/α communication rounds within one epoch. With this we only need an upper bound for the number of epochs N . This is derived by summing (13) over all epochs, then using Lemma 6.1 and Lemma 6.3 to bound the left hand side.Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [NA] Justification: Our theoretical paper does not present any experimental results.Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.• The full details can be provided either with the code, in appendix, or as supplemental material. 
conclusions: 
 We propose the algorithms Async-NLin-UCB and Async-NLSVI-UCB to tackle multi-agent nonlinear contextual bandits and MDPs with asynchronous communication. We prove that our algorithms enjoy low regret and communication cost, which are comparable to previous results.Our algorithms employ a communication criterion that allows the agents to trigger communication rounds, effectively controlling communication cost while promoting the asynchronous protocol.Moreover, we carefully design the contents of server download to guard against data exposure.Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [NA] Justification: Our theoretical paper does not present any experimental results.Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.• The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).• The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)• The assumptions made should be given (e.g., Normally distributed errors).• It should be clear whether the error bar is the standard deviation or the standard error of the mean.• It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified.• For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).• If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [NA] Justification: Our theoretical paper does not present any experimental results.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.• The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.• The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.• The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [Yes] Justification: See Impact Statement before appendices Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.• Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.• The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.• If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: Our theoretical paper does not present any experimental results, and thus does not feature such data and models.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.• Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.• We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [NA] Justification: Our paper does not include any such assets.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL.• The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.• If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset.• For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. 
 
 Appendix: Our work has the potential to enhance cooperative learning systems across diverse fields. By introducing algorithms that enable efficient collaboration among agents with minimal communication overhead, our research paves the way for advancements in distributed systems, including robotics, traffic management, and distributed sensor networks. This could lead to more adaptive, efficient, and scalable systems capable of tackling complex problems in dynamic environments, ultimately contributing to technological progress and societal well-being.As far as we can tell, there is hardly any negative social impact from our work, mainly because we do not include experiments apart from our theoretical analysis.A The Bandit Case: Proof of Theorem 4.3Before we begin the analysis of Algorithm 1, we reiterate and add some notations for clarity and convenience. Define the data collected by agent m that has already been uploaded to the server by round t as Z up m,t , and the universal data at round t as Z all t . Apart from these we also have from the algorithm the datasets Z loc m,t and Z ser t . It is not difficult to check that they satisfy the following relation:Z all t = M m=1 Z up m,t ∪ Z loc m,t .Furthermore, when t is not a communication round, we also haveZ ser t = M m=1 Z up m,t ,and when it is a communication round thatZ ser t = M m=1 Z up m,t ∪ Z loc mt,t ,which will be useful in our proof of Lemma A.1 and B.1 in Section C.1.Next, we assume that at rounds0 = t 0 < t 1 < • • • < t L < t L+1 = T + 1, the participating agentcommunicates with the server, where t 0 and t K+1 are dummy rounds. The subscripts will be denotedas l = 1, • • • , L in the future.We now describe a participant reordering trick for our asynchronous multi-agent setting, which we will use multiple times in the proof. The basic idea is that, as long as the communication order remains the same, and for any given agent, the number of rounds between two consecutive communication rounds remains the same, one can switch the episodes around and change the order of agent participation to a certain degree. For example, we may assume that m t = m t l for all t ∈ (t l-1 , t l ] by reordering the participants, which means all participation of any given agent happens immediately before a certain communication round; as another example, we may assume m t = m t l-1 for all t ∈ [t l-1 , t l ), which means all participation happen immediately after communication rounds. It should be noted that one needs to be careful when utilizing this argument, since switching the participation order changes the values of t l and many associated elements, so applying this trick twice in succession would lead to contradictions.For a dataset Z, we define the Z-norm on function set F as ∥f ∥ 2 Z := (a,r)∈Z f 2 (a) for any f ∈ F. Then we have the shortened notationD λ,F (a; Z) = sup f1,f2∈F |f 1 (a) -f 2 (a)| λ + ∥f 1 -f 2 ∥ 2 Z .Finally, we define the confidence set of functions at round t + 1 as:EQUATIONwhich is a common construction in reinforcement learning.In this section we present some auxiliary lemmas that will be used in the proof of Theorem 4.3. Note these lemmas correspond well to the lemmas presented in 6, only that these are for the contextual bandit case. The proofs for these lemmas can be found in Section C.Lemma A.1. For any t ∈ [T ], m ∈ [M ] and f 1 , f 2 ∈ F, as long as agent m does not communicate with the server at time step t, we haveλ + m ′ ∈[M ] ∥f 1 -f 2 ∥ 2 Z up m ′ ,t ≥ 1 α ∥f 1 -f 2 ∥ 2 Z loc m,t.Furthermore, for any t ∈ [T ] and f 1 , f 2 ∈ F,λ + ∥f 1 -f 2 ∥ 2 Z ser t ≥ 1 1 + M α λ + ∥f 1 -f 2 ∥ 2 Z all t ,and as a corollary, for any a ∈ A,D 2 λ,F (a; Z ser t ) ≤ (1 + M α)D 2 λ,F (a; Z all t )This lemma describes the discrepancy between different datasets. Crucially, it provides a worst case ratio between uncertainty measured on the server dataset and universal dataset. This is an important tool for bridging between the different uncertainty estimators in the following proofs. The proof can be found in Section C.1.Lemma A.2. By taking γ = O(1/T ) andβ t = β 1 := C β,1 √ λ + (γ 2 + γR)T + RC(M, α) log(3M N (F, γ)/δ) , with C β,1 = 6, where C(M, α) := √ 1 + M α + M √ α, we have f * ∈ F t+1 for all t ∈ {t l } L l=1 withprobability at least 1 -δ. As a corollary, we also have |f* (a) -f t+1 (a)| ≤ b t+1 (a) for any a ∈ A t and t ∈ {t l } L l=1 .This is the central optimism lemma present in all provably efficient reinforcement learning literature.It states that the confidence function set contains the ground truth function f * with high probability, and in our case, that the decision function f t + b t is optimistic. With this, we define the good event We segment the entire run ofE T = {f * ∈ F t+1 , ∀t ∈ {t l } L l=1 }. Then according to A.2, P(E T ) ≥ 1 -δ.t = 1, • • • , T into N epochs as follows. Define iteratively 0 = l 0 < l 1 < • • • < l N ≤ L as l i = min l > l i-1 : l l ′ =li-1+1 (a,r)∈Z loc m,t l ′ D 2 λ,F (a; Z ser t l i-1 ) ≥ 1 ,where for a given l ′ in the summation, m = m t l ′ is the participating agent at t l ′ . In the iterative process, if the above minimum does not exist, simply define N = i -1 and end the process there.Correspondingly, the i-th epoch is defined by the time steps [t li-1 , t li ).The following sections will make use of this epoch scheme as befit their needs, but here we shall give an upper bound for the total number of epochs N . Based on the definition of l i , we have for anyEQUATIONfor any a, and so1 ≤ (a,r)∈Z ser t l i \Z ser t l i-1 D 2 λ,F (a; Z ser t l i-1 ) = li l=li-1+1 (a,r)∈Z ser t l \Z ser t l-1 D 2 λ,F (a; Z ser t l i-1 ) ≤ 2 li l=li-1+1 (a,r)∈Z ser t l \Z ser t l-1 D 2 λ,F (a; Z ser t l-1 ),and summing over i = 1, • • • , N -1 that:N -1 ≤ 2 L l=1 (a,r)∈Z ser t l \Z ser t l-1 D 2 λ,F (a; Z ser t l-1).If we apply the participant reordering trick and let m t = m t l for all t ∈ (t l-1 , t l ] and l ∈ [L], we getZ ser t l \Z ser t l-1 = {(a t , r t )} t l t=t l-1 +1, and so applying Lemma A.1 and Lemma A.3, we getN -1 ≤ 2 L l=1 t l t=t l-1 +1 D 2 λ,F (a t ; Z ser t l-1 ) ≤ 2(1 + M α) L l=1 t l t=t l-1 +1 D 2 λ,F (a t ; Z all t-1 ) ≤ 2(1 + M α) T t=1 D 2 λ,F (a t ; Z all t-1 ) ≤ C(1 + M α) dim E (F, λ/T ) log(T /λ) log T,which gives the order of total number of epochs:EQUATION)Notice that the participant reordering trick is only used to bound the number of epochs, which itself does not depend on the specific order of participation. This is crucial since it suggests this reordering does not change anything essential, and is in fact not necessary for the proof -it just made the proof easier to read. Therefore we can still reorder participants as we see fit in other parts of our proof. EQUATIONwhere the first inequality is due to |f | ≤ 1 from Assumption 3.1, and the second inequality again uses Lemma A.2. We first bound the second term here using the epoch scheme in Section A.2. We start by converting the bonus term to uncertainty:EQUATIONNow consider the episodes in an epoch i, specifically {t li-1 , t li-1+1 , • • • , t li }. For any l i-1 < l < l i , since Z sert l i-1⊆ Z ser t l-1 , we can deduce thatD 2 λ,F (z t l ; Z ser t l-1 ) ≤ D 2 λ,F (z t l ; Z ser t l i-1 ) ≤ 2D 2 λ,F (z t l ; Z ser t l ),where the second inequality is borrowed from (15) from Section A.2. Therefore continuing from (18),EQUATION)Now combine this result with the first term in (17) and use again (18), we getReg(T ) ≤ 2C B L l=1 t l+1 -1 t=t l +1 D λ,F (a t ; Z ser t l ) β 2 t l + λ + 2 √ 2C B L l=1 D λ,F (z t l ; Z ser t l ) β 2 h + λ + 4N ≤ 2 √ 2C B L l=1 t l+1 -1 t=t l D λ,F (a t ; Z ser t l ) β 2 t l + λ + 4N ≤ 2 √ 2C B L l=1 t l+1 -1 t=t l D 2 λ,F (a t ; Z ser t l ) 1/2 T t=1 β 2 1 + λ 1/2 + 4Nwhereβ 1 = C β √ λ + RC(M, α) log(3N ()M/δ) .According to Lemma A.1 and Lemma A.3, the termL l=1 t l+1 -1 t=t l D 2 λ,F (a t ; Z ser t l ) ≤ (1 + M α) L l=1 t l+1 -1 t=t l D 2 λ,F (a t ; Z all t-1 ) = (1 + M α) T t=1 D 2 λ,F (a t ; Z all t-1 ) ≤ C(1 + M α) dim E (F, λ/T ) log 2 T / min{1, λ} .combining this with ( 16), we getReg(T ) ≤ C (1 + M α) dim E (F, λ/T ) log 2 T / min{1, λ} 1/2 T t=1 (β 2 t + λ) 1/2 + 4N = O √ T β 1 (1 + M α) dim E (F, λ/T ) log(T / min{1, λ}) + (1 + M α) dim E (F, λ/T ) log 2 (T / min{1, λ}) .In this section we prove the second part of Theorem 4.3, by calculating the communication complexity. First, for each communication round t l , assume the last time before t l when the agent m t l communicated with the server was t l ′ , then(a,r)∈Z loc m,t l D 2 λ,F (a; Z up m,t l ) ≥ (a,r)∈Z loc m,t l b t l ′ (a)/C 2 β 2 t l ′ + λ ≥ α C 2 ,Now employing the epoch segmentation scheme from section A.2, for the i-th epoch consisting of the time steps [t li-1 , t li ), we have the inequality1 ≥ li-1 l=li-1+1 (a,r)∈Z loc m,t l D 2 λ,F (a; Z ser t l i-1 ) ≥ li-1 l=li-1+1 (a,r)∈Z loc m,t l D 2 λ,F a; Z up m,t l ∪ Z ser t l i-1.For m ∈ [M ], assume the agent m communicated with the server a total of n m times within [t li-1 , t li ).Then except for the first of these communication rounds, for each l ∈[l i-1 + 1, l i -1] with m t l = m, there exists l ′ ∈ [l i-1 , l) with m t l ′ = m, thus we have Z up m,t l ⊃ Z up m,t l ′ +1 = Z ser t l ′ ⊃ Z ser t l i-1. With this we have the corresponding term(a,r)∈Z loc m,t l D 2 λ,F (a; Z up m,t l ∪ Z ser t l i-1 ) = (a,r)∈Z loc m,t l D 2 λ,F (a; Z up m,t l ) ≥ α C 2 B , therefore 1 ≥ M m=1 (n m -1) • α 4C 2 ⇒ M m=1 n m ≤ M + C 2 B α Notice that M m=1 n m = l i -l i-1is the number of communication rounds within [t li-1 , t li ), hence summing over i the total number of communication rounds is upper bounded by N (M + C 2 B /α). Combine this with (16), we have the total number of communication rounds throughout the algorithm isO (1 + M α) 2 α dim E (F, λ/T ) log 2 T / min{1, λ} .B The MDPs Case: Proof of Theorem 5.1Similar to the bandit case, we define Z loc m,k,h , Z up m,k,h , Z ser k,h , and Z all k,h to be the local, uploaded, server and universal data, with corresponding subscripts of agent m ∈[M ], episode k ∈ [K], h ∈ [H]. Suppose at rounds 0 = k 0 < k 1 < • • • < k L < k L+1 = T + 1, the participating agent communicates with the server, where k 0 and k L+1 are dummy rounds.For a dataset Z h in the MDPs setting, we again define the Z h -norm on function set F h as ∥f ∥ 2 Z := o h ∈Z f 2 (z h ) for any f ∈ F. As a reminder, the tuples o h = (s h , a h , r h , s h+1 ) and z h = (s h , a h ). Then we have the shortened notationD λ,F h (z h ; Z h ) = sup f1,f2∈F h |f 1 (z h ) -f 2 (z h )| λ + ∥f 1 -f 2 ∥ 2 Z h .Finally, we define the confidence set of functions at round k + 1 and step h as:EQUATION)In this section we present some auxiliary lemmas that will be used in the proof of Theorem 5.1. These lemmas are generalizations / restatements to the lemmas presented in 6, and their detailed proofs can be found in Section C.Lemma B.1 (Restatement of Lemma 6.3). For any k ∈ [K], m ∈ [M ], h ∈ [H]and f 1 , f 2 ∈ F, as long as agent m does not communicate with the server at episode k, we haveλ + m ′ ∈[M ] ∥f 1 -f 2 ∥ 2 Z up m ′ ,k,h ≥ 1 α ∥f 1 -f 2 ∥ 2 Z loc m,k,h.k ∈ [K] and f 1 , f 2 ∈ F, λ + ∥f 1 -f 2 ∥ 2 Z ser k,h ≥ 1 1 + M α λ + ∥f 1 -f 2 ∥ 2 Z all k,h, and as a corollary, for any z = (s, a) ∈ S × A,EQUATIONz; Z all k,h ) Similar to Lemma A.1, this lemma provides a worst case ratio between uncertainty measured on the server dataset and universal dataset. The proof can be found in Section C.1. Lemma B.2 (Restatement of Lemma 6.1). By taking γ = 1/(C γ KH) with C γ ≥ 20, as well asβ k,h = β 2 := C β,2 √ λ + HC(M, α) log(3HM N h (γ)/δ) , with C β,2 = 12 for all k ∈ [K] and h ∈ [H], where N h (γ) = N (F h , γ) • N (F h+1 , γ) • N (W h+1 , γ),we have with probability at least 1-δ that T h Q k+1,h+1 ∈ F k+1,h for all k ∈ {k l } L l=1 with probability at least 1 -δ. As a corollary, we also have|T h Q k+1,h+1 (s, a) -f k+1,h (s, a)| ≤ b k+1,h (s, a) for any (s, a) ∈ S × A, k ∈ {k l } L l=1 and h ∈ [H].This is the central optimism lemma. It states that the Bellman operator of Q-value function at level h + 1 is within the confidences set at level h. The conclusion immediately gives the optimism inequality T h Q k+1,h+1 (s, a) ≤ Q k+1,h (s, a), which we will use at the start of the regret upper bound prove. The proof of the lemma can be found in Section C.2.With this, we define the good eventE T = {T h Q k+1,h+1 ∈ F k+1,h , ∀k ∈ {k l } L l=1 , h ∈ [H]}. Then according to Lemma B.2, P(E T ) ≥ 1 -δ.Lemma B.3. For some absolute constant C D , the following holds for all level h ∈ [H]:K k=1 D 2 λ,F (z k h ; Z all k-1,h ) ≤ C D dim E (F, λ/T ) log 2 (T / min{1, λ})This lemma is essentially the same as Lemma A.3. It reveals the relationship between the sum of Eluder-like confidence quantities and the Eluder dimension. The proof can be found in Section C.3.In this section, we introduce the epoch segmentation scheme for MDPs, which is again needed for both the regret and communication cost proofs presented in the next two sections. All of this is quite similar to the bandit case in Section A.2, but the introduction of multiple levels h ∈ [H] does complicate things a bit.We segment the entire run of episodes k = 1, • • • , K into N epochs as follows. Define iteratively0 = l 0 < l 1 < • • • < l N ≤ L as l i = min l > l i-1 : l l ′ =li-1+1 H h=1 o h ∈Z loc m,k l ′ ,h D 2 λ,F h (z h ; Z ser k l i-1 ,h ) ≥ 1 ,where for a given l ′ in the summation, m = m k l ′ is the participating agent at k l ′ . In the iterative process, if the above minimum does not exist, simply define N = i -1 and end the process there.Correspondingly, the i-th epoch is defined by the episodes [k li-1 , k li ).The following sections will make use of this epoch scheme as befit their needs, but here we shall give an upper bound for the total number of epochs N . Based on the definition of l i , we have for anyEQUATIONfor any h ∈ [H] and z h ∈ S × A, and so1 ≤ li l=li-1+1 H h=1 o h ∈Z loc m,k l ,h D 2 λ,F h (z h ; Z ser k l i-1 ,h ) ≤ 2 li l=li-1+1 H h=1 o h ∈Z ser k l ,h \Z ser k l-1 ,h D 2 λ,F h (z h ; Z ser k l-1 ,h ),and summing over i = 1, • • • , N -1 that:N -1 ≤ 2 H h=1 L l=1 o h ∈Z ser k l ,h \Z ser k l-1 ,h D 2 λ,F h (z h ; Z ser k l-1 ,h).k = m k l for all k ∈ (k l-1 , k l ] and l ∈ [L], we get Z ser k l ,h \Z ser k l-1 ,h = {o k h } k l k=k l-1 +1, and so applying Lemma 6.3 and Lemma 6.2, we getN -1 ≤ 2 H h=1 L l=1 k l k=k l-1 +1 D 2 λ,F h (z k h ; Z ser k l-1 ,h ) ≤ 2(1 + M α) H h=1 L l=1 k l k=k l-1 +1 D 2 λ,F h (z k h ; Z all k-1,h ) ≤ 2(1 + M α) H h=1 K k=1 D 2 λ,F h (z k h ; Z all k-1,h ) ≤ CH(1 + M α) dim E (F, λ/T ) log(T /λ) log T,which gives the order of total number of epochs:EQUATION)In this section, we prove the first half of Theorem 5.1, which gives an upper bound for the cumulative regret of Algorithm 2.Using the participant reordering trick, assume without loss of generality that the same agent is activewithin the rounds [k l , k l+1 -1], i.e. m k l = m k l +1 = • • • = m k l+1 -1 . Under this assumption, we have k 1 = 1.We first prove via induction thatQ * h ≤ Q m,k,h for any m ∈ [M ], k ∈ [K] and h ∈ [H +1].This holds true for h = H + 1 trivially since both value functions at H + 1 are uniformly 0. Suppose we already haveQ * h+1 ≤ Q m,k,h+1, we have from Lemma B.2 that for the last communication round k ′ for agent m, the server functions satisfyT h Q k ′ +1,h+1 (s, a) ≤ f k ′ +1,h (s, a) + b k ′ +1,h (s, a) = Q k ′ +1,h (s, a). Couple this with the fact that Q m,k,h = Q k ′ +1,h , we can prove that Q * h = T h Q * h+1 ≤ T h Q m,k,h+1 ≤ Q m,k,h , which finishes the induction process. Now let a k * h := argmax a∈A Q * h (s k h , a) be the best action at time t, then V * h (s k h ) = Q * h (s k h , a k * h ) ≤ Q m,k,h (s k h , a k * h ) ≤ Q m,k,h (s k h , a k h ),where the second inequality is due to the choice of a k h at round k. Hence we getEQUATION)where the second equality uses the Value-decomposition Lemma from Jiang et al. [2017] , the second inequality uses again Lemma B.2, and from the third inequality onward we let k ′ be the last time agent m communicated with the server.We now bound the second term here using the epoch scheme in Section B.2. We start by converting the bonus term to uncertainty:EQUATION)Now consider the episodes in an epoch i,specifically {k li-1 , k li-1+1 , • • • , k li }. For any l i-1 < l < l i , since Z ser k l i-1 ,h ⊆ Z ser k l-1 ,h , we can deduce that D 2 λ,F h (z k l h ; Z ser k l-1 ,h ) ≤ D 2 λ,F h (z k l h ; Z ser k l i-1 ,h ) ≤ 2D 2 λ,F h (z k l h ; Z ser k l ,h), where the second inequality is borrowed from ( 21) from Section B.2. Therefore continuing from (24),EQUATION)Now combine this result with the first term in ( 23) and use again ( 24), we getReg(K) ≤ C B L l=1 k l+1 -1 k=k l +1 H h=1 D λ,F h (z k h ; Z ser k l ,h ) β 2 h + λ + √ 2C B L l=1 H h=1 D λ,F h (z k l h ; Z ser k l ,h ) β 2 h + λ + N H ≤ √ 2C B L l=1 k l+1 -1 k=k l H h=1 D λ,F h (z k h ; Z ser k l ,h ) β 2 h + λ + N H ≤ √ 2C B L l=1 k l+1 -1 k=k l H h=1 D 2 λ,F h (z k h ; Z ser k l ,h ) 1/2 K k=1 H h=1 β 2 h + λ 1/2 + N H.According to Lemma 6.3 and Lemma 6.2, the termL l=1 k l+1 -1 k=k l H h=1 D 2 λ,F h (z k h ; Z ser k l ,h ) ≤ (1 + M α) L l=1 k l+1 -1 k=k l H h=1 D 2 λ,F h (z k h ; Z all k-1,h ) ≤ (1 + M α) K k=1 H h=1 D 2 λ,F h (z k h ; Z all k-1,h ) ≤ H(1 + M α) dim E (F, λ/T ) log(T /λ) log T.Now with γ = O(1/KH), we haveβ h = O(1)β h+1 + C β √ λ + H (1 + M α) log(3HN h (γ)/δ) + M α log(3HM N h (γ)/δ) therefore, with C(M, α) = √ 1 + M α + M √ αand the upper bound for number of epochs N in ( 22), we haveL l=1 k l+1 -1 k=k l +1 H h=1 b k l ,h (z k h ) ≤ O H(1 + M α) dim E (F, λ/K) log 2 (K/ min{1, λ}) 1/2 K H h=1 (β 2 h + λ) 1/2 + HN = O H √ K β 2 (1 + M α) dim E (F, λ/K) log(K/ min{1, λ}) + H 2 (1 + M α) dim E (F, λ/K) log 2 (K/ min{1, λ}) ,whereβ 2 = C β,2 √ λ + HC(M, α) log HM N (F, γ)N (W, γ)/δ is the choice of β k,h in the algorithm.Next up, we calculate the communication complexity of Algorithm 2 and prove the second half of Theorem 5.1. For each communication round k l , assume the last time before k l when the agent m = m k l communicated with the server was k l ′ , then by the communication rule there existsh l ∈ [H] such that o h l ∈Z loc m,k l ,h l b 2 k l ′ ,h l (z h l )/(β 2 k l ′ ,h l + λ) ≥ α, o h l ∈Z loc m,k l ,h l D 2 λ,F h l (z h l ; Z up m,k l ,h l ) ≥ o h l ∈Z loc m,k l ,h l b k l ′ ,h l (z h l )/C 2 β 2 k l ′ ,h l + λ ≥ α C 2 ,Next we will make use of the epoch segmentation scheme in Section B.2. For the i-th epoch consisting of the time steps [k li-1 , k li ), we have the inequality1 ≥ li-1 l=li-1+1 H h=1 o h ∈Z loc m,k l ,h D 2 λ,F h (z h ; Z ser k l i-1 ,h ) ≥ li-1 l=li-1+1 H h=1 o h ∈Z loc m,k l ,h D 2 λ,F h z h ; Z up m,k l ,h ∪ Z ser k l i-1 ,h . For m ∈ [M ], assume the agent m communicated with the server a total of n m times within[k li-1 , k li ).Then except for the first of these communication rounds, for each l∈ [l i-1 + 1, l i -1] with m k l = m, there exists l ′ ∈ [l i-1 , l) with m k l ′ = m, thus we have Z up m,k l ,h ⊃ Z up m,k l ′ +1,h = Z ser k l ′ ,h ⊃ Z ser k l i-1 ,h for all h ∈ [H]. With this we have H h=1 o h ∈Z loc m,k l ,h D 2 λ,F h z h ; Z up m,k l ,h ∪ Z ser k l i-1 ,h = H h=1 o h ∈Z loc m,k l ,h D 2 λ,F h z h ; Z up m,k l ,h ≥ α 4C 2 , therefore 1 ≥ M m=1 (n m -1) • α 4C 2 ⇒ M m=1 n m ≤ M + 4C 2 α Notice that M m=1 n m = l i -l i-1is the number of communication rounds within [k li-1 , k li ), hence summing over i the total number of communication rounds is upper bounded by N (M + 4C 2 /α). Combine this with the result in ( 22), we have the total number of communication rounds throughout the algorithm isO H (1 + M α) 2 α dim E (F, λ/K) log 2 (K/ min{1, λ}) .In this section we prove all the auxiliary lemmas in Section A.1 and Section B.1. Note that some of these lemmas are very similar in nature, for which we will only give the proof for the version for the MDPs case, and briefly remark on the version for the bandit case.C.1 Proof of Lemma A.1 and Lemma B.1Here we prove Lemma B.1 in detail. The proof for Lemma A.1 is very similar, and so we will only give a short remark on how to apply this to the bandit case.Proof of Lemma B.1. First, for an episode k ∈ [K] and agent m ∈ [M ] such that m does not communicate with the server at episode k (either m is not participating or k is not a communication round), from the communication criterion we haveα ≥ o h ∈Z loc m,k,h b 2 m,k,h (a) β 2 k ′ ,h + λ ≥ o h ∈Z loc m,k,h D 2 λ,F h (z h ; Z ser k ′ ,h ) = o h ∈Z loc m,k,h sup f1,f2∈F h |f 1 (z h ) -f 2 (z h )| 2 λ + ∥f 1 -f 2 ∥ Z ser k ′ ,h ≥ sup f1,f2∈F h ∥f 1 -f 2 ∥ 2 Z loc m,k,h λ + ∥f 1 -f 2 ∥ 2 Z ser k ′ ,h,where k ′ is the last communication round for agent m. This means that for anyf 1 , f 2 ∈ F h , (1/α)∥f 1 -f 2 ∥ 2 Z loc m,k,h ≤ λ + ∥f 1 -f 2 ∥ 2 Z ser k ′ ,h . Observing that Z ser k ′ ,h ⊂ Z ser k,h = M m ′ =1 Z up m ′ ,k,h proves the first conclusion that 1 α ∥f 1 -f 2 ∥ 2 Z loc m,k,h ≤ λ + M m ′ =1 ∥f 1 -f 2 ∥ 2 Z up m ′ ,k,h.Second, for any f 1 , f 2 ∈ F h , from the above conclusion we have for any k ∈[K]\{k l } L l=1 that λ + ∥f 1 -f 2 ∥ 2 Z ser k,h = λ + M m=1 ∥f 1 -f 2 ∥ 2 Z up m,k,h ≥ 1 M α M m=1 ∥f 1 -f 2 ∥ 2 Z loc m,k,h = 1 M α ∥f 1 -f 2 ∥ 2 Z all k,h \Z ser k,h, and when k = k l for some l ∈ [L], we have alternativelyλ + ∥f 1 -f 2 ∥ 2 Z ser k,h = λ + m ′ ̸ =mt ∥f 1 -f 2 ∥ 2 Z up m ′ ,k,h + ∥f 1 -f 2 ∥ 2 Z up m k ,k,h ∪Z loc m k ,k,h ≥ λ + M m=1 ∥f 1 -f 2 ∥ 2 Z up m,k,h ≥ 1 (M -1)α m ′ ̸ =m k ∥f 1 -f 2 ∥ 2 Z loc m ′ ,k,h ≥ 1 M α ∥f 1 -f 2 ∥ 2 Z all k,h \Z ser k,h.Either way, we can deduce for any k ∈ [K] that(1 + M α) λ + ∥f 1 -f 2 ∥ 2 Z ser k,h ≥ λ + ∥f 1 -f 2 ∥ 2 Z all k,h.Finally, from the above we immediately haveD 2 λ,F (z h ; Z ser k,h ) = sup f1,f2∈F h [f 1 (z h ) -f 2 (z h )] 2 λ + ∥f 1 -f 2 ∥ 2 Z ser k,h ≤ (1 + M α) sup f1,f2∈F [f 1 (z h ) -f 2 (z h )] 2 λ + ∥f 1 -f 2 ∥ 2 Z all k,h = (1 + M α)D 2 λ,F (a; Z all k,h ).Remark C.1. Notice that this prove does not depend on the multi-level structure of episodic MDPs, but is a direct result of the communication criterion and protocol. This means the proof can be converted to the bandit case of Lemma A.1 without any essential changes: simply change episode k into time step t, disregard all mentions of level h, and consider z = a instead of z = (s, a).We begin with the proof of Lemma A.2, which is an almost direct application of Lemma D.3.Proof of Lemma A.2. We invoke Lemma D.3 with ϵ 0 = 0, then with probability at least 1 -δ, for allt ∈ {t l } L l=1 , (a,r)∈Z ser t f t+1 (a)-f * (a) 2 ≤ C ERM λ+γ 2 T +γT R+R 2 (1+M α) log(3N/δ)+R 2 M 2 α log(3N M/δ) ≤ β 2 1 ,if we let γ = O(1/T ) be sufficiently small and takeβ 1 = C β,1 √ λ + RC(M, α) log(3M N (F, γ)/δ) with C β,1 = √ C ERM = 6. Thus taking β t = β 1 , accord- ing to the definition of F t+1 , this directly implies f * ∈ F t+1 .With this, since the bonus function satisfyb t+1 (a) ≥ |f 1 (a) -f 2 (a)|, ∀f 1 , f 2 ∈ F s.t. (a,r)∈Z ser t f 1 (a) -f 2 (a) 2 ≤ β 2 t ,which is based on the first property of the bonus oracle in Definition 4.1, by taking f 1 = f t+1 andf 2 = f * we get for any a ∈ A that b t+1 (a) ≥ |f * (a) -f t+1 (a)|, which finishes the proof.Next we prove Lemma B.2, which is more challenging and requires an analysis on the least squares value iteration method.Proof of Lemma B.2. Take F h+1,γ as a γ-cover of F h+1 , and W h+1,γ as a γ-cover of W h+1 . Selectfk+1,h+1 ∈ F h+1,γ W h+1,γ so that ∥Q k+1,h+1 -fk+1,h+1 ∥ ∞ ≤ ε := (1 + β k+1,h+1 )γ. For o h = (s h , a h , r h , s h+1 ), define the corresponding y h = r h + V k+1,h+1 (s h+1 ) and ȳh = r h + sup a∈A fk+1,h+1 (s h+1 , a). Let f k+1,h = argmin f h ∈F h o h ∈Z ser k,h f h (s h , a h ) -ȳh 2 .Then we haveo h ∈Z ser k,h f k+1,h (s h , a h ) -ȳh 2 1/2 ≤ o h ∈Z ser k,h f k+1,h (s h , a h ) -y h 2 1/2 + ε√ k ≤ o h ∈Z ser k,h f k+1,h (s h , a h ) -y h 2 1/2 + ε√ k ≤ o h ∈Z ser k,h f k+1,h (s h , a h ) -ȳh 2 1/2 + 2ε √ k.h = T h fk+1,h (s h , a h ), and the difference ȳh -T h fk+1,h (s h , a h ) is bounded in [-H, H], hence we may apply Lemma D.3 with f * = T h fk+1,h , r t = ȳh , R = H, ϵ 0 = 2ε and δ = δ/3HN (F h+1 , γ) • N (W h+1 , γ), taking a union bound over f ∈ F h+1,γ W h+1,γ and h ∈ [H], we have o h ∈Z ser k,h f k+1,h (s h , a h ) -T h Q k+1,h+1 (s h , a h ) 2 1/2 ≤ o h ∈Z ser k,h f k+1,h (s h , a h ) -T h fk+1,h+1 (s h , a h ) 2 1/2 + γ √ k ≤ C ERM λ + (γ + 2ε) 2 K + (γ + 2ε)KH + H 2 (1 + M α) log(3HN h (γ)/δ) + H 2 M 2 α log(3HM N h (γ)/δ) + γ √ k ≤ C ERM √ λ + γ(3 + 2β k+1,h+1 ) √ K + γ(3 + 2β k+1,h+1 )KH + HC(M, α) log(3HM N h (γ)/δ) ,whereN h (γ) = N (F h , γ) • N (F h+1 , γ) • N (W h+1 , γ). By taking γ = 1/(C γ KH) with sufficiently large absolute constant C γ (for example, C γ = 20), the second and third terms within the bracket above are both less than (1/2)β k+1,h+1 , and hence we can easily prove via induction on h that the above is no greater than β 2 , whereβ 2 = C β,2 √ λ + HC(M, α) log(3HM N (γ)/δ) with C β,2 = 2 √ C ERM = 12 and N (γ) = max h∈[H] N h (γ).In this section we prove Lemma B.3 in detail. The proof for Lemma A.3 is very similar, and so we will again only give a short remark on how to apply this to the bandit case.Proof of Lemma B.3. We fix the level h ∈ [H] throughout the proof. For an index setK 0 ⊆ [K], we denote Z(K 0 ) := {z k h : k ∈ K 0 }.First, let n = ⌈log(K/λ)/ log 2⌉, and we divide the set of episodes K = [K] into n + 1 disjoint episode sets as follows. For any 1 ≤ l ≤ L and k l ≤ k < k l+1 , let( fk,1 , fk,2 ) = argmax f1,f2∈F h f 1 (z k h ) -f 2 (z k h ) 2 λ + ∥f 1 -f 2 ∥ 2 Z all h,k-1, and define L k : S × A → R as L k (z) = fk,1 (z) -fk,2 (z) 2 . Now we define K ι := {k ∈ K :L k (z k h ) ∈ (2 -ι-1 , 2 -ι ]} for ι ∈ {0, 1, • • • , n -1} and K n := {k ∈ K : L k (z k h ) ∈ [0, 2 -n ]}. We note that for k ∈ K n , L k (z k h ) ≤ λ/K.Now define the mapping τ : [K] → [K], such that for any k ∈ [K], τ (k) is the last episode when agent m k communicated with the server (not including k). We will boundk∈K ι D 2 λ,F h (z k h ; Z all h,k-1 ) for ι ∈ {0, • • • , n -1}.For a fixed ι ≤ n -1, we now decomposeK ι = n ι +1 j=1 K ι j , where n ι = |K ι |/ dim E (F h , 2 -ι-1 ) .We start off each set K ι j = ∅, and fill them up gradually by iterating through k ∈ K ι one by one in increasing order to decide which subset K ι j should k belong to. Specifically, we define j(k) to be the smallest index j < n ι such that is z k h is 2 -(ι+1)/2 -independent of Z(K ι j ), and assign k to the set K ι j(k) . If such a j does not exist, we simply let j(k) = n ι + 1 assign k to K ι n ι +1 . Finally after the assignment process, we defineK ι j,k = K ι j ∩ [k] for any k ∈ [K].Then we have the elements added into K ι j(k)-1,k form a sequence where each data corresponding to a new member is 2 -(ι+1)/2 -independent of the old members, and so there are no more than dim E (F h , 2 -ι-1 ) members within each of them. Moreover, for all k ∈ K ι that z k h is 2 -(ι+1)/2 -dependent on each ofZ(K ι 1,k ), • • • , Z(K ι j(k)-1,k ).Now for any k ∈ K ι by the definition of K ι , we have fk,1 (z k h )-fk,2 (z k h ) 2 ≥ 2 -ι-1 . This combined with the 2 -ι-1 -dependencies imply that for eachj ′ = 1, • • • , j(k)-1, ∥ fk,1 -fk,2 ∥ 2 Z(K ι j ′ ,k ) ≥ 2 -ι-1 . Notice that Z(K ι j ′ ,k ) ⊂ Z all h,k-1 for any j ′ ∈ [j(k) -1], and that Z(K ι j ′ ,k ) for j ′ ∈ [j(k) -1] are disjoint, therefore (j(k) -1)2 -ι-1 ≤ j(k)-1 j ′ =1 ∥ fk,1 -fk,2 ∥ 2 Z(K ι j ′ ,k ) ≤ ∥ fk,1 -fk,2 ∥ 2 Z all h,k-1 . It follows that D 2 λ,F h (z k h ; Z all h,k-1 ) = fk,1 (z k h ) -fk,2 (z k h ) 2 λ + ∥ fk,1 -fk,2 ∥ 2 Z all h,k-1 ≤ 2 -ι λ + (j(k) -1)2 -ι-1 = 2 (j(k) -1) + 2 ι+1 λ ,where the first inequality uses the definition of K ι . Summing over k ∈ K ι , we havek∈K ι D 2 λ,F h (z k h ; Z all h,k-1 ) = n ι +1 j=1 k∈K ι j D 2 λ,F h (z k h ; Z all h,k-1 ) ≤ n ι j=1 2 K ι j (j -1) + 2 ι+1 λ + 2 K ι n ι +1 n ι + 2 ι+1 λ ≤ 2 dim E (F h , 2 -ι-1 ) 2 ι+1 λ + n ι j=2 2 dim E (F h , 2 -ι-1 ) j -1 + 2 K ι • dim E (F h , 2 -ι-1 ) K ι ≤ dim E (F h , 2 -ι-1 ) 2 log n ι + 4 + 1/(2 ι λ) ,where we used the relationK ι j ≤ dim E (F h , 2 -ι-1) and the definition of n ι in the second inequality.Additionally, for ι = n we also havek∈K n D 2 λ,F h (z k h ; Z all h,k-1 ) ≤ k∈K n L k (z k h ) λ ≤ |K n | • λ/K λ ≤ 1,and so finally we sum over ι = 0, • • • , n to getK k=1 D 2 λ,F h (z k h ; Z all h,k-1 ) ≤ n-1 ι=0 dim E (F h , 2 -ι-1 ) 2 log n ι + 4 + 1/(2 ι λ) + 1 ≤ n dim E (F h , 2 -n ) 2 log K + 4 + 1/λ + 1 ≤ C dim E (F h , λ/K) log(K/ min{1, λ}),where the final step makes the assumption that λ = O(1/ log K), in which case it holds with some absolute constant C D .Remark C.2. Again, this prove does not depend on the multi-level structure of episodic MDPs. In fact, it only relies on the Eluder dimensionality of F h . This means the proof can be converted to the bandit case of Lemma A.3 without any essential changes: simply change episode k into time step t, disregard all mentions of level h, and consider z = a instead of z = (s, a).In this section, we provide a technical concentration lemma that serves as the core of our results. For one, this lemma is based on the following concentration inequality:Lemma D.1. For a sequence of random variables {Z t } t∈N adapted to the filtration {S t } t∈N and function f ∈ F, for any λ > 0, with probability at least 1 -δ, for all t ∈ N, we have- 1 λ t s=1 log E exp[-λf (Z s )] S s-1 - t s=1 f (Z s ) ≤ 1 λδ .The proof for this lemma can be found under Lemma 4 of Russo and Van Roy [2013] . Apart from this, we need yet another basic concentration lemma:Lemma D.2. Suppose {η t } T t=1 is a sequence of conditional R-sub-Gaussian random variables satisfying E e µηt H t-1 ≤ exp R 2 µ 2 /2 , where H t-1 denotes all history before time t, with probability 1 -δ, we haveT t=1 η 2 t ≤ 2T σ 2 + 3σ 2 log(1/δ).A proof of this lemma can be found under Lemma G.2 of Ye et al. [2023] . With this, we can prove the following lemma characterizing the accuracy of least squares solution. Even though we need this lemma for both bandit and RL settings, we will follow the notations presented in multi-agent contextual bandits. Detailed explanation of how this translates to multi-agent MDPs can be found in Section C.2.Lemma D.3. Suppose we have a sequence of inputs {(a t , r t )} T t=1 that follow the rule r t = f * (a t )+η t for some ground truth f * ∈ F, with η t being conditionally R-sub-Gaussian:E e µηt a 1:t , r 1:t-1 ≤ exp(R 2 µ 2 /2), ∀µ ∈ R.We also have server datasets Z ser t at different time steps, collected following the communication protocol in our settings. Note that strictly speaking, the conditions under which η t is sub-Gaussian should also include the former participants m 1:t , but we will omit this dependency for convenience.Consider f ser t+1 , the approximate ERM solution to the least squares problem:(a,r)∈Z ser t f ser t+1 (a) -r 2 1/2 ≤ min f ∈Ft (a,r)∈Z ser t f (a) -r 2 1/2 + ϵ 0 √ t,Then abbreviating N = N (F, γ) and taking C ERM = 36, with probability at least 1 -δ,(a,r)∈Z ser t f ser t+1 (a) -f * (a) 2 ≤ C ERM λ + (γ + ϵ 0 ) 2 T + (γ + ϵ 0 )T R + R 2 (1 + M α) log(3N/δ) + R 2 M 2 α log(3N M/δ)Proof of Lemma D.3. Let F γ be a γ-cover of the function class F with respect to the infinity norm ∥ • ∥ ∞ . For f ∈ F and (a t , r t ) for some t ∈ [T ], letϕ(f, a t , r t ) = -(f (a t ) -r t ) 2 + (f * (a t ) -r t ) 2 ,Since r t = f * (a t ) + η t , we can write ϕ(f, a t , r t ) asϕ(f, a t , r t ) = -f (a t ) -f * (a t ) + η t 2 + η 2 t = -2 f (a t ) -f * (a t ) η t -f (a t ) -f * (a t ) 2Since η t is R-sub-Gaussian conditional on Z all t-1 , a t , we have for any positive parameter µ thatlog E exp(µϕ(f, a t , r t )) Z all t-1 , a t ≤ 2µ 2 R 2 (f (a t ) -f * (a t )) 2 -µ(f (a t ) -f * (a t )) 2 = (2µ 2 R 2 -µ)(f (a t ) -f * (a t )) 2Using Lemma D.1, we have with probability at least 1 -δ/3, for all f ∈ F γ and t ∈ [T ],EQUATIONwhere µ all > 0 is a parameter we will determine later.On the other hand, if we consider any local agent m, when m t = m, we have η t is R-sub-Gaussian conditional on Z up m,t-1 ∪ Z loc m,t-1 and a t , i.e. all the data agent m has received from the environment up to this point. Thus we have for any µ > 0 thatEQUATIONNow for f ser t+1 , there exists f ∈ F γ such that ∥ f -f ser t+1 ∥ ∞ ≤ γ. Using Lemma D.2, this gives us the following with probability at least 1 -δ/3:- (a,r)∈Z ser t ϕ( f , a, r) = (a,r)∈Z ser t f (a) -r 2 -f * (a) -r 2 ≤ (a,r)∈Z ser t f ser t+1 (a) -r 2 + tγ 2 2 - (a,r)∈Z ser t f * (a) -r 2 ≤ (a,r)∈Z ser t f * (a) -r 2 + √ t(γ + ϵ 0 ) 2 - (a,r)∈Z ser t f * (a) -r 2 = (γ + ϵ 0 ) 2 t + 2(γ + ϵ 0 ) √ t t s=1 η 2 s 1/2 ≤ (γ + ϵ 0 ) 2 t + 2(γ + ϵ 0 ) 2T 2 R 2 + 3T R 2 log(3/δ),where we used the basic inequality (a + b) 2 ≤ a 2 + b 2 in the first inequality and used the property of f ser t+1 in the second inequality. Finally, taking a union bound and combining this with (28), we have with probability at least 1 -δ,(a,r)∈Z ser t f ser t+1 (a) -f * (a) 2 ≤ 2γ 2 t + 2 (a,r)∈Z ser t f (a) -f * (a) 2 ≤ 2γ 2 t -2 (a,r)∈Z ser t ϕ( f , a, r) + λ + 32R 2 (1 + M α) log(3N/δ) + 32R 2 M 2 α log(3N M/δ) ≤ 2γ 2 T + 2(γ + ϵ 0 ) 2 T + 4(γ + ϵ 0 ) 2T 2 R 2 + 3T R 2 log(3/δ) + λ + 32R 2 (1 + M α) log(3N/δ) + 32R 2 M 2 α log(3N M/ ≤ C ERM λ + (γ + ϵ 0 ) 2 T + (γ + ϵ 0 )T R + R 2 (1 + M α) log(3N/δ) + R 2 M 2 α log(3N M/δ) ,where the first inequality uses again ∥ f -f ser t+1 ∥ ∞ ≤ γ, and it can be verified that the last inequality holds when C ERM ≥ 36.NeurIPS Paper Checklist 


Decision: This paper studied asynchronous multi-agent reinforcement learning with general function approximation. Both regret and communication complexity have been analyzed, with solid theoretical derivations. However, there were concerns regarding the technical novelty of the results, and presentation/writing of the results. There were also some concerns regarding the tightness of the bounds. After reading the paper more carefully, I found the majority of the techniques and quantities follow closely from those in single-agent RL with general function approximation, which diminishes the novelty of the technical contributions. Moreover, the lack of experiments to validate the theories made the impact of the results relatively limited, beyond purely theoretical arguments. In general, it is a borderline paper, and the paper could benefit from the review feedback this round.

Reviews: review: paper_summary: paper_summary: This paper studied the distributed federated contextual bandit and federated reinforcement learning (FRL) in the presence of a trusted server. In both problems, nonlinearity and asynchronous communications are explored. Similar algorithms for contextual bandit and FRL that encourage exploration via bonus functions are proposed. Finite-time convergence results in terms of regrets are established for both algorithms and communication complexities are also characterized.
strength_weakness: strength_weakness: * The clarity of some of the important quantities are not well defined or explained. For example, 
1)	In the sample complexity result of Theorem 4.3, $\tilde{\beta}_1$ is used. However, it was not defined. It’s unclear what this notation is referring to. Similarly, in Theorem 5.1, $\tilde{\beta}_2$ is used.
2)	The oracle for to compute bonus term bk+1,h is crucial in understanding the algorithms. However, it was not very well-explained or shown anywhere in the main paper.	
3)	The two sentences from Line 300 to Line 302 are confusing. Please clarify them.
* Typos:
1)	An extra closing parenthesis appeared in Line 141.
2)	Line 214, ?? -> 12
3)	In Line 1 of algorithm 3, $k=[K]$ -> $k\in [K]$.
4)	In Line 154, the trajectory should be $(s_h, a_h, \cdots, s_H, a_H)$.
questions: questions: * What if there are more than one agents are to be activated instead of just having one agent at each time t?
* How is an agent chosen to be activated in Line 5 of both Algorithm 1 and 2?
* What is the oracle to compute the bonus term?
* What are the terms $\tilde{\beta}_1$ and $\tilde{\beta}_2$?
* Please clarify the two sentences from Line 300 to Line 302.
limitations: limitations: Please see weaknesses and questions.
paper_summary: paper_summary: This paper studies the asynchronous multi-agent bandit and RL problem with general function approximation (measured by Elude dimension). The main contribution is to establish $\tilde{O}(\sqrt{\text{dim} T})$ regret bound with $\tilde{O}(M^2 \text{dim})$ communication complexity.
strength_weakness: strength_weakness: I think the major concern is non-optimal complexity bounds. Although it seems unreasonable to ask for a matching upper\&lower regret bound for the contextual bandit problem, the part about RL could be possibly improved (at least, the dependence on $H$ is not tight). Also I am curious that what is the current best lower bound for the communication cost to reach an $\sqrt{T}$ regret bound. It would be an interesting problem to study the exact trade-off between the communication cost and regret.

A minor concern might be about the technical novelty given previous methods on measuring the uncertainty.
questions: questions: What is the meaning of "fully asynchronous" in table 1?
limitations: limitations: Yes.
paper_summary: paper_summary: The authors propose two algorithms for asynchronous communication in multi-agent reinforcement learning with generalized value function approximation: Asynchronous-NLin-UCB for context bandit scenarios and Asynchronous-NLSVI-UCB for episodic MDP scenarios. These algorithms achieve near-optimal regret with low communication complexity. The authors theoretically show the trade-off between regret and communication complexity.
strength_weakness: strength_weakness: While I have studied general value function approximation, I do not have research background in this field for multi-agent scenarios. Therefore, my critique may not have captured the weaknesses of this paper. 
I’m open to revising my score based on the authors' responses.

As far as I know, MARL often adopts the Centralized Training Decentralized Execution(CTDE) framework to avoid the action space growing exponentially with the number of users. However, it is unclear whether the proposed scenario follows "decentralized execution". Agents are supposed to execute based on partial observations in a decentralized manner, but the proposed approach appears to involve a central server consistently during execution. If the proposed scenario is inconsistent with CTDE, I would be interested to hear from the authors what the distinct advantages or necessity of this scenario is.

Typos:

- Line 214: Reference to the label is not correctly written.
- Theorems 4.3 and 5.1: $\tilde{\beta}$ is not properly defined in the statement, and $\beta_t$ should be fixed to $\tilde{\beta}$.
- Theorem 5.1: Total communication complexity should be fixed to $O((1+M\alpha)^2 / \alpha)$.
questions: questions: A simple question: Why is the order of the Eluder dimension of regret reported as $O(\sqrt{\text{dim}_E})$ instead of $O(\text{dim}_E)$? The regret in Line 677 shows similar results to numerous other papers, but is written in $\sqrt{O(\text{dim}_E)}$ despite the fact that $O(\text{dim}_E)$ dominates. For the linear MDP case, [1] presents a lower bound of $\Omega(dH\sqrt{T})$, and considering $\text{dim}_E = \tilde{O}(d)$, the reported results seem lower than the known lower bound. Many papers report similar results as the authors, but am I missing something?

[1] Zhou Dongruo, Quanquan Gu, and Csaba Szepesvari. "Nearly minimax optimal reinforcement learning for linear mixture Markov decision processes." Conference on Learning Theory. PMLR 2021.
limitations: limitations: The requirement for global state instead of partial observation may limit the practical applicability of the proposed methods.
paper_summary: paper_summary: In this paper, the authors study multi-agent reinforcement learning where agents cooperate through asynchronous communications with a central server to learn a shared environment. They consider the following two settings: multi-agent contextual bandits with general function approximation, and multi-agent RL with general function approximation. For both settings, they propose provably efficient algorithms with low regret and low communication complexity.
strength_weakness: strength_weakness: 1. It seems that part of the techniques is from previous results, such as the bonus function oracle. It will be helpful if there is a section discussing technical novelty.

2. It seems that the setting is closely related to low switching RL and RL with delayed feedback. It will be interesting if the authors could briefly discuss about the connections.

3. For the communication complexity bound in theorem 5.1, should it be $/\alpha$ instead of $\alpha$? In addition, why not choose $\alpha=1/M$ in both theorems? In this way, the communication cost can be improved. (Please correct me if I misunderstood anything) 

4. Line ?? in line 214 of page 6. Please correct it.
questions: questions: Please refer to the weaknesses above.
limitations: limitations: Yes.

Comments: title: Response to Comment
Thank you for the response
Response to Follow-up Question
Response to rebuttal
comment: Thanks for your detailed response. I will keep my score.
Thanks to the reviewers once again for their detailed response. I believe this paper makes a significant contribution to the analysis of federated RL in GVFA, and I will raise my score to 7.
Thank you for the response! We’re glad to hear that we have resolved many of your questions. Regarding the contribution of our work compared with multi-agent RL in the linear MDP setting, we outline some of the main challenges and technical innovations below. The first two challenges are mentioned in the contributions section of our paper (Lines 56-62), but we did not discuss the third one due to its complex technical nature and limited space. 

- First, our approach to designing the **communication content** (download data) differs significantly from previous work in linear MDPs. For multi-agent communication in a linear environment, one can utilize the closed-form solution for least squares regression and transmit the covariance matrix. However, for general function classes, no explicit solution exists. Thus, we developed a data transmission policy consisting of decision functions and bonus functions. This protocol avoids transmitting the entire dataset, which could result in data leakage, and does not require the sending confidence function sets, which is impractical in a nonlinear context.


- Another major innovation is our **communication criterion**. The communication criterion in linear MDPs is based on the degree of increment in covariance matrix determinant. Adapting the criterion directly to general function approximation settings is challenging due to the absence of a closed-form solution to linear regression and a counterpart to covariance matrices. 


    Our criterion relies on uncertainty estimators. Intuitively, a communication round is triggered when the local agent collects a substantial amount of new data compared to old data, implying that the data collected for each communication round grows exponentially, and thus communication frequency decays exponentially as well. To the best of our knowledge, the communication criterion we proposed is the first effective criterion for multi-agent nonlinear RL, achieving a regret logarithmically dependent on the number of agents while also maintaining logarithmic communication cost with respect to $T$ and $K$.


- One particular technical difficulty arises when bounding the communication cost, as we need to bound the summation of bonus functions across all local data concerning the previous server update $Z^{\text{ser}}$ (see eq(8)). In particular, our Lemma 6.2 provides an upper bound for the summation of uncertainty concerning global data history $Z^{\text{all}}$. The **discrepancy between server data $Z^{\text{ser}}$ and global data $Z^{\text{all}}$** presents a unique challenge, requiring careful analysis of uncertainty estimators. This involves navigating between these different datasets using the epoch segmentation scheme (see Appendix A.2 & B.2). This issue also arises in multi-agent linear MDP settings, but it is much simpler to address when uncertainties are measured by matrices.
At this point, the author's answers seem to have resolved many of the questions I initially had, and I have a better understanding of their contribution to this field. However, I am still concerned that the paper is simply an extension of linear MDPs to general value function approximation. 
Can the authors explain what new problems they encountered and solved in this extension?
The authors' detailed response has addressed my concern. The reviewer has revised the score.
Thank you for the follow-up question! 

We first point out that in theory, we assume data upload, calculation of decision function $\hat{f}$ and bonus function $b$, as well as function download are all instantaneous (Lines 12-20 in Algorithm 2), so the proposed scenario will never occur and hence does not affect our theoretical analysis. 

That being said, should we implement our algorithm in practice, we believe this scenario is also very unlikely to happen for the following reasons: 
1. As per our communication criterion in equation (8), each agent only communicates with the server once their local sum of uncertainty accumulates to $\alpha$, which means **the frequency of communication decreases exponentially** relative to round $K$. Therefore, when $K$ is large, the communication frequency becomes extremely low, which means the probability of overlap is also very low; 
2. In order to avoid communication overhead when $K$ is small, one may consider initializing all local agents with some initial observations before deploying our asynchronous algorithm. This ensures that local agents will not start communicating until their observed data exceed a certain threshold. 

Finally, even without the assumption that communication is instantaneous, it is not difficult to modify our theoretical analysis to accommodate for overlapping communication and **delayed feedback**. If we simply ask the agent to **adhere to the old policy** until the updates are received, under proper assumptions the regret term will be incremented by $O(\log K)$ in the worst case. A large body of literature addresses optimization and bandits with delayed feedback, offering analysis techniques we could potentially leverage. However, extending our current methods in this direction is beyond the scope of our current work, therefore we do not consider it in our paper.
I appreciate the authors' efforts on the response. I have one follow-up question with regard to A4. I am wondering the validity of the following scenario:

In multi-agent setting, in particular when the number of agents is sufficiently large, the probability of two agents communicating with the server having an overlap time seems to be up to the switch condition. If the switch condition is easy to be satisfied, then the above probability is not negligible. In the case that an overlap does happen, an active sampling agent A who just satisfied the switch condition may have to wait for the server to finish processing the request (line 11 and 12) of another active agent B. The processing time may also take significant time depending on the new data size.

Is above scenario possible to occur? Thanks.
Thanks for the response. I will adjust my score after discussion with AC and other reviewers.