Randomized Exploration in Cooperative Multi-Agent Reinforcement Learning

Authors: hao-lun  hsu
weixin  wang
miroslav  pajic
pan  xu
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-12 18:56:42

Abstract: We present the first study on provably efficient randomized exploration in cooperative multi-agent reinforcement learning (MARL). We propose a unified algorithm framework for randomized exploration in parallel Markov Decision Processes (MDPs), and two Thompson Sampling (TS)-type algorithms, CoopTS-PHE and CoopTS-LMC, incorporating the perturbed-history exploration (PHE) strategy and the Langevin Monte Carlo exploration (LMC) strategy respectively, which are flexible in design and easy to implement in practice. For a special class of parallel MDPs where the transition is (approximately) linear, we theoretically prove that both CoopTS-PHE and CoopTS-LMC achieve a $\widetilde{\mathcal{O}}(d^{3/2}H^2\sqrt{MK})$ regret bound with communication complexity $\widetilde{\mathcal{O}}(dHM^2)$, where $d$ is the feature dimension, $H$ is the horizon length, $M$ is the number of agents, and $K$ is the number of episodes. This is the first theoretical result for randomized exploration in cooperative MARL. We evaluate our proposed method on multiple parallel RL environments, including a deep exploration problem (i.e., $N$-chain), a video game, and a real-world problem in energy systems. Our experimental results support that our framework can achieve better performance, even under conditions of misspecified transition models. Additionally, we establish a connection between our unified framework and the practical application of federated learning.

Main paper: 
 introduction: 
 Multi-Agent Reinforcement Learning (MARL) has emerged as a potent tool with wide-ranging applications in diverse fields including robotics [23, 54] , gaming [74, 92, 84] , and numerous realworld systems [10, 25, 85] . This is particularly evident in cooperative scenarios, where MARL's effectiveness is enhanced through both direct and indirect communication channels among agents. This requires MARL algorithms to adeptly and flexibly coordinate communications to optimize the benefits of cooperation. One of the classical challenges in MARL is balancing exploration and exploitation so that agents effectively utilize existing information while acquiring new knowledge. Recent literature highlights the intricacies of this balance, focusing on cooperative exploration strategies [27] and dynamic exploitation tactics [68] . Achieving this equilibrium is crucial for the practical deployment of MARL systems in real-world scenarios, where unpredictability and the need for rapid adaptation are prevalent [27, 14, 55] .Optimism in the Face of Uncertainty (OFU) is a popular strategy to address the explorationexploitation problem [1] . OFU strategy leads to numerous upper confidence bound (UCB)-type algorithms in contextual bandits [18, 1, 50] , single-agent reinforcement learning [36, 76] , and more recently multi-agent reinforcement learning [24, 56] . These algorithms compute statistical confidence regions for the model or the value function, given the observed history, and perform the greedy policy with respect to these regions, or upper confidence bounds. Though UCB-based methods give out strong theoretical results, they often have poor performance in practice [61, 60] . For example, Wang et al. [76] demonstrates that computing the confidence bonus necessitates advanced sensitivity sampling and the expensive computation makes the practical applications inefficient. It is worth noting that UCB is mostly constructed based on a linear structure [18, 36] . NeuralUCB is a notable attempt at a nonlinear version while it is infeasible in terms of computational complexity [94, 82] .Inspired by Thompson Sampling (TS) [73] , posterior sampling for reinforcement learning (RL) [7, 95] involves maintaining a posterior distribution over the parameters of the Markov Decision Processes (MDP) model parameters. Although conceptually simple, most existing TS methods require the exact posterior or a good Laplacian approximation [83] . Recently, there have been advancements in randomized exploration with approximate sampling. One important method is perturb-history exploration (PHE) strategy, which involves introducing random perturbations in the action history of the agent [45, 47, 32] . This randomized exploration approach diversifies the agent's experience, aiding in learning more robust strategies in environments with uncertainty and variability. Another effective method is Langevin Monte Carlo (LMC) method [83, 33, 31, 42, 58, 34] . Notably, Ishfaq et al. [33] maintains the simplicity and scalability of LMC, making it applicable in deep RL algorithms by approximating the posterior distribution of the Q function.Despite the aforementioned advancements of randomized exploration in bandits and single-agent RL, there remains a scarcity of research on randomized exploration within cooperative MARL, which motivates us to present the first investigation into provably efficient randomized exploration in cooperative MARL, with both theoretical and empirical evidence. We specifically focus on the applicability in parallel MDPs, aiming to facilitate faster learning and to improve policy optimization with the same state and action spaces, allowing for leveraging similarities across MDPs. We theoretically and empirically demonstrate that randomized exploration strategies can be extended to the multi-agent setting and the benefit of randomized exploration instead of UCB can be significant from single-agent to multi-agent setting.In summary, our contributions are as follows:• We propose a unified algorithm framework for learning parallel MDPs, and apply two TS-related strategies PHE and LMC for exploration, which leads to the CoopTS-PHE and CoopTS-LMC algorithms. Unlike conventional TS, which suffers from sampling errors due to Laplace approximation and expensive posterior computation [66, 46] , our proposed algorithms only require adding standard Gaussian noises to the dataset (CoopTS-PHE) or the gradient (CoopTS-LMC) when performing Least-Square Value Iteration, which is efficient in computation and avoids sampling bias due to the Laplace approximation. Notably, both algorithms are easily implementable which are more practical than UCB-based algorithms in deep MARL. • When reduced to linear parallel MDPs, we theoretically prove that both CoopTS-PHE and CoopTS-LMC with linear function approximation can achieve a regret bound O d 3/2 H 2 √ M √ dM γ + √ K with communication complexity O (d + K/γ)M H , where d is the feature dimension, H is the horizon length, M is the number of agents, K is the number of episodes for each agent, and γ is a parameter controlling the communication frequency. When γ = O(K/dM ), our algorithms attain O d 3/2 H 2 √ M K regret with O(dHM 2 ) communication complexity. This result matches the best communication complexity in cooperative MARL [56] , and the best regret bounds for randomized RL in the single-agent setting (M = 1) [32, 33] . A comprehensive comparison with baseline algorithms on episodic, non-sationary, linear MDPs is presented in Table 1 .• We further extend our theoretical analysis to the misspecified setting where both the transition and reward are approximately linear up to an error ζ and the MDPs could be heterogeneous across agents, which is a generalized notion of misspecification [36] . We theoretically prove when ζ = O d/M K , the cumulative regret for CoopTS-PHE matches the result in the linear homogeneous MDP setting. Simultaneously, when ζ = O 1/M K , the cumulative regret for CoopTS-LMC matches the result in the linear homogeneous MDP setting. This result indicates that CoopTS-PHE has a slightly higher tolerance on the model misspecification than CoopTS-LMC. • We conduct extensive experiments on various benchmarks with comprehensive ablation studies, including N -chain that requires deep exploration, Super Mario Bros task in a misspecified setting, and a real-world problem in thermal control of building energy systems. Our empirical evaluation demonstrates that our randomized exploration strategies outperform existing deep Q-network Table 1 : Comparison on episodic, non-stationary, linear MDPs. We define the average regret as the cumulative regret divided by the total number of samples (transition pairs) used by the algorithm.Here d is the feature dimension, H is the episode length, K is the number of episodes, and M is the number of agents in a multi-agent setting.  
preliminary: 
 In parallel Markov Decision Processes (MDPs), M agents interact independently with their respective discrete-time MDPs, sharing the same but independent state and action spaces. Each agent might have its unique reward functions and transition kernels. Specifically, for agent m ∈ M, the associated MDP is defined by the tuple MDP(S, A, H, P m , r m ). Here S and A are the state and action spaces respectively, H is the horizon length, P m = {P m,h } h∈ [H] and r m = {r m,h } h∈ [H] are the sets of transition kernels and reward functions. For step h ∈ [H], P m,h (•|s, a) is the probability measure over the next state given current state-action pair (s, a), r m,h : S × A → [0, 1] is the deterministic reward function. The policy π m = {π m,h } h∈[H] is a sequences of decision rules where π m,h : S → A is the deterministic policy at step h.For agent m ∈ M, given any policy π and transition P, to evaluate the policy effectiveness in the m th MDP, we define value function V π m,h (s) := E π [ H h ′ =h r m,h ′ (s m,h ′ , a m,h ′ )|s m,h = s] and Q function Q π m,h (s, a) := E π [ H h ′ =hr m,h ′ (s m,h ′ , a m,h ′ )|s m,h = s, a m,h = a] for any (h, s, a) ∈ [H]×S ×A. The optimal policy is defined as π * m , and we denote V * m,h (s) = V π * m m,h (s). For each k ∈ [K], at the beginning of episode k, each agent m ∈ M receives the initial state s k m,1 chosen arbitrarily by the environment. For each step h ∈ [H] in this episode, each agent m observes its current state s k m,h , selects an action a k m,h based on policy π k m,h , receives a reward r m,h (s k m,h , a k m,h ), and then transitions to the next state s k m,h+1 based on the transition probability measure P m,h (•|s k m,h , a k m,h ). The reward defaults to 0 when the episode terminates at step H + 1. The goal of agents is to minimize the cumulative group regret after K episodes, which is defined asRegret(K) = m∈M K k=1 V * m,1 s k m,1 -V π k m m,1 s k m,1 . 
algorithm design: 
 In this section, we first present a unified algorithm framework for conducting randomized exploration in cooperative MARL. Then we introduce two practical randomized exploration strategies.A unified algorithm framework is presented in Algorithm 1, where each agent executes Least-Square Value Iteration (LSVI) in parallel and makes decisions based on collective data obtained from communication between each agent and the server. Before we describe the details of our algorithm, we first define notations about the datasets stored on each agent's local machine and the server. Receive initial state s k m,1 .5:V k m,H+1 (•) ← 0.{Q k m,h (•, •)} H h=1 ←Randomized Exploration ◁ Algorithm 2 or Algorithm 3 7:for step h = 1, ..., H do 8:a k m,h ← argmax a∈A Q k m,h (s k m,h , a). before episode k where synchronization happens. For episode k and step h, we define three datasets:EQUATIONEQUATIONEQUATIONBy definition, U ser h (k) is the dataset that is shared across all agents due to the latest synchronization at episode k s . U loc m,h (k) is the unique data collected by agent m since episode k s . Then U m,h (k) is the total dataset available for agent m at the current time. Let K(k) = |U m,h (k)| be the total number of data points. For the simplicity of notation, we also re-order the data points in U m,h (k), and rename the tuple (s τ m,h , a τ m,h , s τ m,h+1 ) as (s l , a l , s ′ l ) such that we have U m,h (k) = K(k) l=1 (s l , a l , s ′ l ). In fact, this can be done by the following one-to-one mappingEQUATIONTherefore, we use indices (s, a, s ′ ) ∈ U m,h (k) and l ∈ [K(k)] interchangeably for the summation over set U m,h (k).Algorithm interpretation At a high level, each episode k in Algorithm 1 consists of two stages.The first stage (Lines 3-15) is parallelly executed by all agents and the second stage (Lines [16] [17] [18] [19] [20] [21] [22] [23] [24] involves the communication among agents and the server.In the first stage (Lines 3-15) of Algorithm 1, each agent m operates in two parts. The first part (Line 6) updates estimated Q functions {Q k m,h } H h=1 through LSVI with a randomized exploration strategy (Algorithm 2 or Algorithm 3, which will be introduced in Section 3.2). In particular, given the estimated value functions V k m,h+1 (•) = max a∈A Q k m,h (•, a) at step h + 1, we perform one step robust backward Bellman update to obtain V k m,h (•) at step h. And we initialize V k m,H+1 (•) to be 0 (Line 5). In the second part (Lines 7-14), after obtaining the estimated Q functions, in each step h we execute the greedy policy with respect to Q k m,h and collect new data points which are added to the local dataset U loc m,h (k) (Lines 8-10). Then we verify the synchronization condition (Lines 11-13). In this paper, we mainly use three types of synchronization rules. (1) We can synchronize every c episode where c is a user-defined constant, which is easy to implement in practice. (2) We can also synchronize at the episode of b 1 , b 2 , ..., b n , with b representing the base of the exponential function. This is guided by the intuition that agents require more transitions urgently at the early learning stages. (3) Additionally, if we have a feature mapping ϕ(s, a) : S × A → R d , based on (3.1), we define the following empirical covariance matrices.ser Λ k h = (s l ,a l ,s ′ l )∈U ser h (k) ϕ s l , a l ϕ s l , a l ⊤ , loc Λ k m,h = (s l ,a l ,s ′ l )∈U loc m,h (k) ϕ s l , a l ϕ s l , a l ⊤ , Λ k m,h = ser Λ k h + loc Λ k m,h + λI.We synchronize as long as the following condition is met:EQUATIONwhere γ is a communication control factor. In our experiments, we try all three rules and compare their performance, which is discussed in detail in Appendix K.1.The second stage (Lines 16-24) is executed only when the synchronization condition is satisfied. First, all the agents upload their local transition set U loc m,h (k), i.e., the newly collected local data after the last synchronization, to the server. Then, the server gathers all information together in U ser h (k) and sends it back to each agent. Finally, each agent resets the local transition setEQUATION, which contains the historical data of all agents up to last synchronization and its local dataset.When we update the model parameter and estimate Q functions in Algorithm 1 (Line 6), we use exploration strategies to avoid suboptimal policies. Previous work adopted Upper Confidence Bound (UCB) exploration in the linear function class [24, 56] to estimate the Q function {Q k m,h } H h=1 . Although UCB-based methods come with strong theoretical guarantees, they often perform poorly in practice [16, 61, 60] . Moreover, UCB requires precise computation of the confidence set, which is usually hard to be implemented beyond the linear structure. In contrast, randomized exploration strategies offer more robust performance, flexibility in design, ease of implementation, and do not require a linear structure.We approximate the Q functions with the following function class F = {f w : S ×A → R|f w (s, a) = f (w; ϕ(s, a))}, where w ∈ R d is the parameter and ϕ ∈ R d is a feature mapping associated with state-action pairs. Now we define the loss function for estimating the Q functions.EQUATIONwhere r l h = r h s l , a l , ϕ l = ϕ s l , a l , and L is a user-specified loss function.The first strategy we use in Algorithm 1 is called the perturbedhistory exploration [45, 47, 32] , displayed in Algorithm 2. We refer to the resulting algorithm as CoopTS-PHE. In particular, we optimize the following randomized loss function, where we add random Gaussian noises to the rewards and regularizer in (3.4) .EQUATIONwhereϵ k,l,n h i.i.d ∼ N (0, σ 2 ), ξ k,n h ∼ N (0, σ 2 I), and n ∈ [N ].Then we obtain the following perturbed estimated parameterEQUATIONNote that we repeat the above steps for n = 1, . . . , N to obtain independent copies of parameters, which is referred to as the multi-sampling process [32, 33] . Then we obtain the estimated Q function Q k m,h based on Line 7 in Algorithm 2. Finally, by maximizing Q k m,h over action space A, we obtain the estimated value function V k m,h .Algorithm 2 Perturbed-History Exploration for n = 1, ..., N do 4: Sample {ϵ k,l,n h } l∈[K(k)] i.i.d∼ N (0, σ 2 ) and ξ k,n h ∼ N (0, σ 2 I) independently.Solve w k,n m,h according to (3.6).end for 7:Q k m,h ← min max n∈[N ] f w k,n m,h ; ϕ , H -h + 1 + . 8: V k m,h (•) ← max a∈A Q k m,h (•, a). 9: end for 10: Output: {Q k m,h (•, •), V k m,h (•, •)} H h=1 .Langevin Monte Carlo Exploration Next we introduce the Langevin Monte Carlo exploration strategy [83, 33] in Algorithm 3, which stems from the Langevin dynamics [67, 8, 19, 81, 96] .Combining it with Algorithm 1 leads to our second proposed algorithm, CoopTS-LMC. Specifically, we update the model parameter iteratively. For iterate j = 1, . . . , J k , the update is given byEQUATIONwhere for n = 1, ..., N do 4:L k m,h is defined in (3.4), ϵ k,j,n m,h ∈ R d is a standard Gaussian noise, η m,EQUATIONfor j = 1, ..., J k do6: Sample ϵ k,j,n m,h i.i.d∼ N (0, I).Update w k,j,n m,h by (3.7).end forend for 10:Q k m,h ← min max n∈[N ] f w k,J k ,n m,h ; ϕ , H -h + 1 + . 11: V k m,h (•) ← max a∈A Q k m,h (•, a). 12: end for 13: Output: {Q k m,h (•, •), V k m,h (•, •)} H h=1 .4 Theoretical Analysis 
homogeneous parallel linear mdps: 
 We provide theoretical analyses of our algorithms in the linear structure under the assumption of linear function approximation and linear MDP setting. We first present the definition of linear MDPs.Definition 4.1 (Linear MDP [36] ). An MDP(S, A, H, P, r) is a linear MDP with feature map ϕ : S × A → R d , if for any h ∈ [H], there exist d unknown measures µ h = (µ 1 h , ..., µ d h ) over S and an unknown vector θ h ∈ R d such that for any (s, a) ∈ S × A,P h (•|s, a) = ϕ(s, a), µ h (•) , r h (s, a) = ϕ(s, a), θ h .Without loss of generality, we assume that for all (s, a) ∈ S × A, ∥ϕ(s, a)∥ ≤ 1 and max{∥µ h (S)∥, ∥θ h ∥} ≤ √ d.Throughout the analyses in this section, we assume the homogeneous parallel MDPs setting where all agents share the same linear MDP defined in Definition 4.1. We also provide the results when the MDPs across agents are approximately linear and heterogeneous, which is deferred to Section 4.2 due to the space limit. Under the linear MDP assumption, it is known that the Q-function admits a linear form [36, Regret(K) = O d 3 2 H 2 √ M dM γ + √ K , with probability at least 1 -δ. Remark 4.3. When we choose γ = O(K/dM ) in the synchronization condition (3.3), the cu- mulative regret of CoopTS-PHE becomes O(d 3/2 H 2 √ M K), which matches the result of UCB exploration [24] . When M = 1, the regret becomes O(d 3/2 H 2 √ K), which matches the existing best randomized single-agent result [32, 33] . Note that if there is no communication at all and agents act independently, with the same number of learning rounds (or samples), the cumulative regret becomes O(M •d 3/2 H 2 √ K). By incorporating communication, our regret bound in Theorem 4.2 is lower than that of the independent setting by a factor √ M . A similar strategy called rare-switching update with a determinant synchronization condition has also been adopted in parallel bandit problems [69, 15] .Similarly, we have the following result for CoopTS-LMC. Theorem 4.4. Under Definition 4.1, choose L to be l 2 loss and linear function class f (w;ϕ l ) = w ⊤ ϕ l in (3.4). In CoopTS-LMC (Algorithm 1+Algorithm 3), let N = C log(δ)/ log(c ′ 0 ) where c ′ 0 = 1 -1/2 √ 2eπ and C = O(d). Let 1/ β m,k = O H √ d for all m ∈ M, λ = 1, and 0 < δ < 1. For any episode k ∈ [K] and agent m ∈ M, let the learning rate η m,k = 1/ 4λ max Λ k m,h , the update number J k = 2κ k log(4HKM d) where κ k = λ max Λ k m,h /λ min Λ k m,h is the condition number of Λ k m,h . Under the determinant synchronization condition (3.3), we have Regret(K) = O d 3 2 H 2 √ M dM γ + √ K ,with probability at least 1 -δ. Remark 4.5. Note that CoopTS-PHE and CoopTS-LMC have the same order of regret. Hence the discussion in Remark 4.3 also applies to CoopTS-LMC. We would also like to highlight that our results are the first rigorous regret bounds for randomized MARL algorithms.From the perspective of technical novelty, our analysis of randomized MARL algorithms is different from that of UCB-based algorithms [24] because the model prediction error here contains randomness, causing a more complex probability analysis and an additional approximation error. We would also like to point out that in proofs for both CoopTS-LMC and CoopTS-PHE we use a new ε-covering technique to prove that the optimism lemma holds for all (s, a) ∈ S ×A instead of just the state-action pairs encountered by the algorithm, which is essential for the regret analysis. This was ignored by previous works [13] and its follow-up works [93, 33] that use the same regret decomposition technique. Furthermore, the multi-agent setting and the communications from synchronization in our algorithms also significantly increase the challenges in our analysis compared to randomized exploration in the single-agent setting [32, 33] .Next we present the communication complexity of Algorithm 1 with synchronization condition (3.3). Lemma 4.6. The total number of communication rounds between the agents and the server in Algorithm 1 is bounded by CPX = O((d + K/γ)M H). Moreover, the total number of transferred random bits only has a logarithmic dependence on the number of episodes K. Remark 4.7. We provide a refined analysis in Appendix C to get this improved result based on that of [24] , which studied the same communication procedure as ours. When we choose γ = O(K/dM ), the communication complexity reduces to O(dHM 2 ), which only has a logarithmic dependence on the number of episodes K. Additionally, we provide a rigorous analysis to show that the algorithm only needs to communicate logarithm number of random bits throughout the learning process.Note that Min et al. [56] studied the asynchronous setting where only one agent is active in each episode, giving out the regret O(d 3/2 H 2 √ K) with the communication complexity O(dHM 2 ). It is interesting to see that our algorithm, though in the synchronous setting, has the same communication complexity as the asynchronous variant. This implies that the asynchronous algorithm can only circumvent current communication by delaying it to the future but does not decrease the communication complexity. In fact, the synchronous setting can learn the policy better in our work, which is indicated by comparison of the average regret (the cumulative regret divided by the total number of samples used by the algorithm) in Table 1 . By achieving a matched communication complexity, we find that synchronous and asynchronous settings have their own advantages and cannot replace each other. This phenomenon can help us better understand the properties of these two communication schemes.In this part, we extend our theoretical analysis to the misspecified setting. In this setting, the transition functions P m,h and the reward functions r m,h are heterogeneous across different MDPs, which is slightly more complicated than the homogeneous setting. Moreover, instead of assuming the transition and reward are linear, we only require each individual MDP is a ζ-approximate linear MDP [36] where both the transition and reward are approximately linear up to an controlled error ζ. over S and an unknown vector θ h ∈ R d such that for any (s, a) ∈ S × A, we haveP m,h (• | s, a) -ϕ(s, a), µ h (•) TV ≤ ζ, r m,h (s, a) -⟨ϕ(s, a), θ h ⟩ ≤ ζ,where ∥ • ∥ TV is the total variation norm, for two distributions P 1 and P 2 , we define it as: ∥P 1 -P 2 ∥ TV = 1 2 x∈Ω |P 1 (x) -P 2 (x)|.Without loss of generality, we assume that ∥ϕ(s, a)∥ ≤ 1 for all (s, a) ∈ S × A, and max ∥µ h (S)∥, ∥θ h ∥ ≤ √ d for all h ∈ [H] and m ∈ M.Remark 4.9. Note that our misspecified setting defined in Definition 4.8 is a generalized notion of misspecification in [36] . Moreover, our misspecified setting is also more general and cover the small heterogeneous setting mentioned in [24] . The triangle inequality can easily be used to derive small heterogeneous setting from our misspecified setting, but not vice versa. Regret(K) = O d 3 2 H 2 √ M dM γ + √ K + dH 2 M √ K dM γ + √ K ζ ,Regret(K) = O d 3 2 H 2 √ M dM γ + √ K + d 3 2 H 2 M √ K dM γ + √ K ζ ,with probability at least 1 -δ.  
experiments: 
 In this section, we present an empirical evaluation of our proposed randomized exploration strategies (i.e., CoopTS-PHE and CoopTS-LMC) with deep Q-networks (DQNs) [57] as the core algorithm on varying tasks under multi-agent settings compared with several baselines: vanilla DQN, Double DQN [28] , Bootstrapped DQN [62] , and Noisy-Net [26] ). Given that all experiments are conducted under multi-agent settings unless explicitly specified as a single-agent or centralized scenario, we denote CoopTS-PHE as "PHE" and CoopTS-LMC as "LMC" in both experimental contexts and figures. Note that we run all our experiments on Nvidia RTX A5000 with 24GB RAM. The implementation of this work can be found at https://github.com/panxulab/MARL-CoopTS The N -chain [62] comprises a sequence of N states denoted as {s l } N l=1 . Assuming the existence of m agents, all initiating their trajectories from s 2 , this study explores the dynamics of their movement within the chain. At each time step, agents face the decision to move either left or right. Notably, each agent incurs a nominal reward of r = 0.001 upon reaching state s 1 , while a more substantial reward of r = 1 is obtained upon reaching the terminal state s N . The illustration of N -chain environment is shown in Appendix K.1. With a horizon length of N + 9, the optimal return is 10. We consider N = 25 with the communication among agents in Figure 1 following the synchronization approach in Algorithm 1. In Figure 1 (a), we show that PHE and Bootstrapped DQN result in higher average episode return among all agents while LMC can also eventually converge to a similar reward.Upon increasing the number of agents to m = 3, we show in Figure 1 (b) that our randomized exploration methods outperform all other baselines. Notably, the fluctuation in PHE is observed to be less pronounced against LMC. This observation lends support to our theoretical framework regarding performance tolerance in the misspecified setting, as detailed in Section 4.2. The complete results for N -chain and ablation studies can be found in Appendix K.1.Environmental heterogeneity, arising from various sources, is a prevalent challenge in practical scenarios. In Section 4.2, we illustrate the extension of homogeneous parallel MDP to the misspecified setting. In the Super Mario Bros task [74] , we examine a scenario where four agents, denoted as m = 4, engage in learning within distinct environments. Despite these environments sharing the same state space S, action space A, and reward function, their characteristics are different described in Appendix K.2. The primary objective of the Super Mario Bros task is to train an agent capable of advancing as far-right and rapidly as possible without collisions or falls. Utilizing preprocessed images as input states, agents aim to select optimal actions from a set of 7 discrete actions.Figure 1 (c) visually depicts that both randomized exploration strategies outperform other baselines in cooperative parallel learning. Notably, We observe that the superiority of LMC gets significant against PHE unlike the results in N -chain in Figures 1(a ) and 1(b). In the case of PHE, Gaussian noise is introduced to the reward before applying the Bellman update, which can be viewed as a method empirically approximating the posterior distribution of the Q function using a Gaussian distribution. However, it is crucial to note that in practical scenarios, unlike the N -chain setting, Gaussian distributions may not always provide an accurate approximation of the true posterior of the Q function [33] . Here, transitions are shared among the four agents whenever the synchronization condition in (3.3) is met. We also conducted extra experiments in this task extending our proposed method to federated learning shown in Figure 1 (d) with details in Appendix K.2.Finally, we assess the efficacy of our randomized exploration strategies through their application to a practical task within a sustainable energy system: BuildingEnv, as outlined in [85] . BuildingEnv is designed to manage the heating supply in a multi-zone building, which involves addressing realworld physical constraints and accounting for environmental shifts over time. The objective is to meet user-defined temperature specifications while simultaneously minimizing overall electricity consumption. We defer the environment details to Appendix K.3. With the availability of different cities in varying weather types, we conduct experiments on multiple cities in parallel and share their data following Algorithm 1 for each exploration strategy. During the evaluation, we deploy those trained policies to the environment of each city/weather respectively. We include all methods as well as random action in Figure 2 for a fair comparison. Specifically, we sample action randomly from action space for random action.We display the distribution of the return with probability density in violin plots, indicating that our PHE and LMC can perform better with a higher mean.Additional results for other cities can be found in Appendix K.3. 
conclusion: 
 We proposed a unified algorithm framework for provably efficient randomized exploration in parallel MDPs. By combining this unified algorithm framework with two TS-type randomized exploration strategies, PHE and LMC, we obtained two algorithms for parallel MDPs: CoopTS-PHE and CoopTS-LMC. These two algorithms are both flexible in design and easy to implement in practice. Under the linear MDP setting, we derived the theoretical regret bounds and communication complexities of CoopTS-PHE and CoopTS-LMC. This is the first result for randomized exploration in cooperative MARL, matching the best existing regret bounds for single-agent RL [32, 33] . We also extended our theoretical analysis to the misspecified setting. Our experiments on diverse RL parallel environments verified that randomized exploration improves the balance between exploration and exploitation in both homogeneous and heterogeneous settings. Future research directions includes extending our randomized exploration algorithm to fully decentralized or federated learning settings. Additionally, developing a more communication-efficient algorithm to reduce the substantial communication costs in the general function class setting is another potential direction. 
 
 Appendix: Cooperative Multi-Agent Reinforcement Learning Cooperative MARL is closely intertwined with the domain of multi-agent multi-armed bandits, exemplified by decentralized algorithms featuring communication across a network or hypergraphs [48, 91, 41] and distributed settings [29, 77] .Cooperative MARL manifests primarily in two categories: multi-agent MDPs [12, 89, 79, 24] and parallel MDPs [11, 24, 53, 11, 56] . In the realm of cooperative multi-agent robotics, the former is employed to formulate optimal multi-agent policies across the distributed system [86, 87] . On the other hand, homogeneous parallel MDPs leverage inter-agent communication to expedite learning processes [43] . Additionally, heterogeneous parallel MDPs establish connections to heterogeneous federated learning [51] and exhibit improved generalizability in transfer learning scenarios [72] .We focus on parallel MDPs in this paper, where agents interact with the environment simultaneously to tackle shared challenges within extensive and distributed systems [43] . Recently, Dubey and Pentland [24] proposed the Coop-LSVI algorithm, extending the LSVI-UCB algorithm [36] in singleagent RL to MARL with linear MDPs. In a parallel RL setting with asynchronous communication, Min et al. [56] builds upon Coop-LSVI while relinquishing compatibility with heterogeneous MDPs. Meanwhile, Lidard et al. [53] focuses on fully decentralized multi-agent UCB Q-learning in a tabular setting, maintaining polynomial space complexity even as the number of agents increases. However, it is worth noting that neither of the previous works [24, 56] in non-tabular cooperative MRAL provides experimental validation for the efficacy of their proposed communication strategies. The gap arises from their reliance on LSVI-UCB as the core algorithm, wherein optimism is instantiated through UCB. Empirical evidence suggests that UCB-based approaches tend to underperform in practical scenarios [61, 60, 33] . Moreover, the computational demands of LSVI-UCB become untenable due to the necessity of recurrently computing the feature covariance matrix for updating the UCB bonus function. On the other hand, distributed applications of parallel MDPs in TS-based concurrent RL algorithms have been explored [21, 22, 17] . Specifically, Dimakopoulou and Roy [21] proposed a tabular model learning method based on seed sampling for coordinated exploration. This approach was further generalized to address intractable state spaces in [22] and supported by a Bayesian regret bound in [17] . However, none of these studies consider the communication complexity associated with efficient cooperative strategies. Therefore, randomized exploration in this work is critical to make these algorithm designs practical.The roots of randomized exploration, particularly TS, can be traced back to its success in bandit problems [73] . Randomized exploration strategies can typically exhibit superior performance in practical applications due to avoidance of early convergence to suboptimal actions [38] [39] [40] . Furthermore, these strategies demonstrate robustness in the face of noise and uncertainty, particularly within non-stationary environments [78, 9] . This success has extended to Langevin Monte Carlo Thompson Sampling (LMCTS), which has been applied to various domains, including linear bandits, generalized linear bandits, and neural contextual bandits [83] . The exploration of posterior sampling techniques in RL has gained prominence, building upon the foundation laid by TS [71, 7] . Randomized Least-Square Value Iteration (RLSVI) is an approach that leverages random perturbations to approximate the posterior, with frequentist regret analysis applied under the tabular MDP setting [63] , inspiring subsequent works focusing on theoretical analyses aimed at improving worst-case regret under tabular MDPs [70, 4] , with extensions to the linear setting [88, 32, 20] . In addition to theoretical advancements, several practical algorithms have been proposed based on RLSVI to approximate posterior samples of Q functions in deep RL. These approaches involve ensembles of randomly initialized neural networks [62, 64] and noise injection into the parameters of the neural network [26, 52] . With the success of LMCTS [83] in bandit domains, the exploration of randomized methods has expanded to alternative approaches like LMC in tabular RL [42] and linear MDPs with neural network approximation [33] . Further works delve into the realm of random exploration from the perspectives of delayed feedback [44] and offline RL [59] .While posterior sampling demonstrates superiority in various contexts, its theoretical foundations in the multi-agent setting remain underexplored. Existing research predominantly focuses on two-player zero-sum games, considering both Bayesian [95, 35] and frequentist regrets [80, 65] . There is no existing work studying randomized exploration for cooperative multi-agent settings.In this section, we specifically discuss our TS-related algorithms in the linear structure, which is under the assumption of linear function approximation and linear MDP setting.Recall from the loss function in (3.4), here we choose L to be l 2 loss and linear function class f (w; ϕ l ) = w ⊤ ϕ l . By solving this least-square regression problem, we obtain the unperturbed regression estimator w k m,h . In the linear setting, we have the closed-form solutionw k m,h = (Λ k m,h ) -1 b k m,h , (B.1)where Λ k m,h and b k m,h are defined as followsΛ k m,h = K(k) l=1 ϕ s l , a l ϕ s l , a l ⊤ + λI, b k m,h = K(k) l=1 r h s l , a l + V k m,h+1 s ′ l ϕ s l , a l .A natural way of doing randomized exploration is to add a noise N (0, σ 2 (Λ k m,h ) -1 ) to w k m,h and get the estimated parameter wk m,h . Then we can construct estimatedQ function Q k m,h (•, •) = min{ϕ(•, •) ⊤ wk m,h , H -h + 1} + .We call this method as CoopTS, which is aligned with other linear TS algorithms [6, 2] . In what follows, we theoretically show that our proposed algorithms are equivalent or approximately converge to the CoopTS algorithm in the linear function approximation setting.For CoopTS-PHE (Algorithm 1+Algorithm 2), let the function approximation in (3.5) be linear and choose L to be the squared loss. By solving this least-square regression problem, we obtain the perturbed regression estimator w k,n m,h in CoopTS-PHE. The following proposition conveys that CoopTS-PHE is actually equivalent to CoopTS.m,h by CoopTS-PHE is equivalent to adding a Gaussian vector to the unperturbed regression estimator w k m,h , i.e.,w k,n m,h = w k m,h + ζ k,n m,h , where ζ k,n m,h ∼ N (0, σ 2 (Λ k m,h ) -1 ).For CoopTS-LMC (Algorithm 1+Algorithm 3), let function approximation in (3.4) be linear and choose L to be l 2 loss to get the loss function. Then after finishing the LMC update, we get the estimated parameter w k,J k ,n m,h and construct the model approximation of Q function. The following proposition conveys that the distribution of w k,J k m,h converges to the posterior distribution of Thompson Sampling exploration. The proof of this proposition is given in [83] . Proposition B.2 (Approximately equivalent to CoopTS [83] ). If the epoch lengthJ k in Al- gorithm 3 is sufficiently large, the distribution of w k,J k m,h converges to Gaussian distribution N ( w k m,h , β -1 m,k (Λ k m,h ) -1).Propositions B.1 and B.2 indicate that the results of our two randomized exploration strategies are closely related to CoopTS. As we have mentioned above, in CoopTS, the estimated parameterwk m,h is sampled from the normal distribution N ( w k m,h , σ 2 (Λ k m,h ) -1). However, in practice, this sampling is often executed in this way: we sample β ∼ N (0, I) first, then we calculate wkm,h = w k m,h + σ(Λ k m,h ) -1 2 β and obtain the estimated parameter. Nevertheless, computing Λ k m,h -1 2can be computationally expensive, often requiring at least O(d 3 ) operations with the Cholesky decomposition, making it impractical for high-dimensional machine learning challenges. Additionally, the Gaussian distribution used in Thompson Sampling may not effectively approximate the posterior distribution in more complex bandit models than the linear MDP due to their intricate structures.Moreover, as pointed out by recent work [16, 66, 46, 83] , the Laplace approximation-based Thompson Sampling exhibits a constant approximation error in the estimation of the posterior distribution. Therefore, it necessitates a careful redesign of the covariance matrix to ensure effective performance.As mentioned above, computing Λ k m,h -12 can be computationally expensive. However, Perturbed-History exploration and Langevin Monte Carlo exploration can avoid this. For PHE, by only adding i.i.d random Gaussian noise to perturb reward and regularizer, its performance will be equivalent to TS. For LMC, by only performing noisy gradient descent, we can do the randomized exploration, resulting in similar performance compared with TS. Additionally, these two methods can easily be implemented to general function class while Thompson Sampling usually cannot be generalized except for the linear setting. In summary, these two methods are both flexible in design and easy to implement in practice.We emphasize that agents can just send compressed statistics to the server under the linear setting, which can largely reduce communication cost. In the linear function class, we can calculate the closed-form solution of the regression problem (B.1). In this case, when synchronization process is met, all the agents will only need to send their calculated local statistics loc Λ k m,h and loc b k m,h to help solve the regression problem. This communication cost is much smaller because Λ is only a d×d matrix and b is only a d-dimensional vector, where d is the feature dimension in linear MDP assumption. This can also avoid privacy disclosure through communications.Nevertheless, in the general function class setting, our proposed algorithms still require sharing all the collected datasets, which will cause relatively large communication cost. Additionally, in Appendix K.2, we also propose a federated setting algorithm Algorithm 4. In this setting, instead of sharing collected datasets, agents can just share the weight of the collected estimated Q functions, which can largely reduce the communication cost.The proof of the communication complexity is largely inspired by that in [24] . However, we provide a refined analysis here, and thus obtain an improved communication complexity O(dHM 2 ), in contrast with the O(dHM 3 ) complexity in their paper. We also discussed this in Remark 4.7 and showed that our result matches that of a recently proposed asynchronous algorithm. Moreover, we do a careful calculation of the total number of transferred random bits and show it only has a dependence on the number of episodes K.Proof of Lemma 4.6. We assume σ = {σ 1 , . . . , σ n } as the synchronization episodes, where σ i ∈ [K], we also denote σ 0 = 0. To bound the number of synchronization n, we separate σ into two parts with an undetermined term αI 1 = {i ∈ [n]|σ i -σ i-1 ≤ α}, I 2 = {i ∈ [n]|σ i -σ i-1 > α}. Then we have n = |I 1 | + |I 2 |. Note that K ≥ σ n = n i=1 (σ i -σ i-1 ) ≥ i∈I2 (σ i -σ i-1 ) > |I 2 |α. Then we have |I 2 | < K/α. Then note that n i=1 log det(Λ σi m,h ) det(Λ σi-1 m,h ) ≥ i∈I1 log det(Λ σi m,h ) det(Λ σi-1 m,h ) ≥ i∈I1 γ σ i -σ i-1 ≥ |I 1 | γ α . (C.1) Define Λ K h = m∈M K k=1 ϕ z k m,h ϕ z k m,h ⊤ + λI where z k m,h = s k m,h , a k m,h . On the other hand, we have n i=1 log det(Λ σi m,h ) det(Λ σi-1 m,h ) = log det(Λ σn m,h ) det(Λ σ0 m,h ) ≤ log det(Λ K h ) det(λI) ≤ d log(1 + M K/d), (C.2)where the first inequality holds due to the trivial fact that A ≼ B ⇒ det(A) ≤ det(B), the second inequality follow from Lemma J.2 and the fact that ∥ϕ(•)∥ 2 ≤ 1. Combine (C.1) and (C.2), then we have|I 1 | ≤ dα/γ log(1 + M K/d).Finally, we choose α = K/d, then we haven ≤ K α + dα γ log 1 + M K d = d + K γ log 1 + M K d .When one synchronization occurs, communications between agents and the server will occur M times because we have M agents in total. Recall from Lines 16-24 in Algorithm 1, also note that in one synchronization episode, communications will happen H times between every agent and the server. Finally, the upper bound of communication complexity isCPX = O (d + K/γ)M H .Next we consider the total number of transferred random bits. We first calculate the communication bits per round. Under the linear setting, we can calculate the closed-form solution of the regression problem ŵkm,h = (Λ k m,h ) -1 b k m,h, whereΛ k m,h = K(k) l=1 ϕ s l , a l ϕ s l , a l ⊤ + λI, b k m,h = K(k) l=1 [r h s l , a l + V k m,h+1 (s ′ l )]ϕ s l , a l . Note that l ∈ [K(k)] is equivalent to (s, a, s ′ ) ∈ U m,h (k), and the index set U m,h (k) consists of U ser h (k) and U loc m,h (k).Therefore, the empirical covariance matrix Λ k m,h and the vector b k m,h can be decomposed into the summation of the local matrices and vectors on each agent. When the synchronization occurs, agents just need to send their local statistics loc Λ k m,h and loc b k m,h to the server to help solve the regression problem on each agent.EQUATIONk) ϕ s l , a l ϕ s l , a l ⊤ , this is the summation of up to K d × d matrices. Note that ∥ϕ(s, a)∥ ≤ 1, thus it is easy to see that the entries of each matrix, namely, ϕ s l , a l ϕ s l , a l ⊤ , are bounded by 1. Therefore, the entries in loc Λ k m,h are bounded by K. For each entry in this matrix, it suffices to use O(log K) bits to communicate between the server and the agent. Thus in each round, O(d 2 log K) bits are needed to send the matrix loc Λ k m,h . For the local vector loc b k m,hloc b k m,h = (s l ,a l ,s ′ l )∈U loc m,h (k) [r h s l , a l + V k m,h+1 (s ′ l )]ϕ s l , a l ,this is a d-dimensional vector. Note that r h is bounded by 1, V k m,h+1 is bounded by H and is linear with ϕ by definition, which indicates we only need to communicate a d-dimensional vector wk m,h to obtain V k m,h+1 . Similar to the above analysis, in each round, O(d log(K(H + 1))) bits are needed to send the vector loc b k m,h . Therefore, the total bits of communication still only has a logarithmic dependency on the number of episodes K. This completes the proof.The general framework for CoopTS-LMC and CoopTS-PHE is closely similar. To make the article more concise, we first prove CoopTS-LMC completely, which is a bit more complicated. Then we can simplify the following similar proof for CoopTS-PHE in Appendix G.Before deriving the regret bound for CoopTS-LMC, we first provide the necessary technical lemmas for our regret analysis. Note that the loop (Line 3-9) in Algorithm 3 is to do multi-sampling for N times. To simplify the notations, we eliminate the index n before Lemma D.7 because the previous lemmas have nothing to do with multi-sampling. Definition D.1 (Model prediction error). For any(m, k, h) ∈ M × [K] × [H],we define the model error associated with the reward r h ,l k m,h (s, a) = r h (s, a) + P h V k m,h+1 (s, a) -Q k m,h (s, a). Definition D.2 (Filtration). For any (m, k, h) ∈ M × [K] × [H], we define the filtration F m,k,h as F m,k,h = σ s τ n,i , a τ n,i (n,τ,i)∈M×[k-1]×[H] s k n,i , a k n,i (n,i)∈[m-1]×[H] s k m,i , a k m,i i∈[h] .Proposition D.3. In Algorithm 3, the parameter w k,J k m,h satisfies the Gaussian distributionN µ k,J k m,h , Σ k,J k m,h, where mean vector and the covariance matrix are defined asµ k,J k m,h = A J k k ...A J1 1 w 1,0 m,h + k i=1 A J k k ...A Ji+1 i+1 I -A Ji i w i m,h , Σ k,J k m,h = k i=1 1 β m,i A J k k ...A Ji+1 i+1 I -A 2Ji i (Λ i m,h ) -1 (I + A i ) -1 A Ji+1 i+1 ...A J k k ,whereA i = I -2η m,i Λ i m,h for i ∈ [k]. Lemma D.4. For any (m, k, h) ∈ M × [K] × [H], the unperturbed estimated parameter w k m,h satisfies w k m,h ≤ 2H M kd/λ. Lemma D.5. Let λ = 1 in Algorithm 3. For any fixed 0 < δ < 1, with probability at least 1 -δ 2 , for any (m, k, h) ∈ M × [K] × [H] and for any (s, a) ∈ S × A, we have ϕ(s, a) ⊤ w k,J k m,h -ϕ(s, a) ⊤ w k m,h ≤ 5 2d log(1/δ) 3β K + 4 3 ∥ϕ(s, a)∥ (Λ k m,h ) -1 .Lemma D.6. Let λ = 1 in Algorithm 3. For any fixed 0 < δ < 1, with probability at least 1 -δ, for any(m, k, h) ∈ M × [K] × [H], we have w k,J k m,h ≤ 16 3 Hd √ M K + 2K 3β K δ d 3/2 def = B δ , Lemma D.7. Let λ = 1 in Algorithm 3. For any fixed 0 < δ < 1, with probability at least 1 -δ, for all (m, k, h) ∈ M × [K] × [H], we have (s l ,a l ,s ′ l )∈U m,h (k) ϕ s l , a l V k m,h+1 -P h V k m,h+1 s l , a l (Λ k m,h ) -1 ≤ 3H √ dC δ ,whereC δ = 1 2 log(K + 1) + log 2 √ 2KB δ/2N M HK H + log 3 δ 1/2and B δ is defined in Lemma D.6. ϕ(s, a) ⊤ w k m,h -r h (s, a) -P h V k m,h+1 (s, a) ≤ 5H √ dC δ ∥ϕ(s, a)∥ (Λ k m,h ) -1 . Lemma D.9 (Error bound). Let λ = 1 in Algorithm 3. Under Definition 4.1, for any fixed 0 < δ < 1, with probability at least 1 -δ -δ 2 , for any (m, k, h) ∈ M × [K] × [H] and for any (s, a) ∈ S × A, we have -l k m,h (s, a) ≤ 5H √ dC δ + 5 2d log √ N /δ 3β K + 4 3 ∥ϕ(s, a)∥ Λ k m,h -1, where C δ is defined in Lemma D.7.Lemma D.10 (Optimism). Let λ = 1 in Algorithm 3 andc ′ 0 = 1 -1 2 √ 2eπ . Under Definition 4.1, for any fixed 0 < δ < 1, with probability at least 1 -|C(ε)|c ′ 0 N -2δ where |C(ε)| ≤ (3/ε) d , for all (m, h, k) ∈ M × [H] × [K]and for all (s, a) ∈ S × A, we havel k m,h (s, a) ≤ α δ ε, where α δ = √ M K 2H √ d + B δ/N M HK .Remark D.11. Here we point out that in our proofs for both CoopTS-LMC and CoopTS-PHE, we use a new ε-covering technique to prove that the optimism lemma holds for all (s, a) ∈ S × A instead of just the state-action pairs encountered by the algorithm, which is essential in applying this lemma to bound the termE π * [l k m,h (s m,h , a m,h )|s m,1 = s k m,1 ] in (D.2) in the regret analysis. This was ignored by previous works [13, 33] that use the same regret decomposition technique in the single-agent setting.The following lemma gives the upper bound of self-normalized term summation in the multi-agent setting, which is first introduced by Lemma 9 in [24] . To make our analysis complete, we give out the proof in the Appendix E.9 where we make some necessary modifications compared with Lemma 9 in [24] . Lemma D.12. Let Algorithm 2 run for any K > 0, M ≥ 1, and γ as the communication control factor. DefineΛ K h = m∈M K k=1 ϕ s k m,h , a k m,h ϕ s k m,h , a k m,h ⊤ + λI, then we have m∈M K k=1 ϕ(s k m,h , a k m,h ) (Λ k m,h ) -1 ≤ log det(Λ K h ) det(λI) + 1 M √ γ + 2 M K log det(Λ K h ) det(λI).The following lemma shows that we can decompose the regret of Algorithm 2 into three different components. The proof of this lemma closely resembles Lemma 4.2 in [13] for the single-agent setting. When we fix the agent m ∈ M, it is totally same as Lemma 4.2 in [13] . Lemma D.13. [13, Lemma 4.2] Define the operators and the following terms:(J m,h f )(s) = f (s, •), π * m,h (•|s) , (J m,k,h f )(s) = f (s, •), π k m,h (•|s) , D m,k,h,1 = J m,k,h Q k m,h -Q π m,k m,h s k m,h -Q k m,h -Q π m,k m,h s k m,h , a k m,h , (D.1) D m,k,h,2 = P m,h V k m,h+1 -V π m,k m,h+1 s k m,h , a k m,h -V k m,h+1 -V π m,k m,h+1 s k m,h+1 .Then we can decompose the regret into the following form:EQUATIONEQUATION.In this part, we give out the proof of Theorem 4.4, the regret bound for CoopTS-LMC.Proof of Theorem 4.4. Based on the result from Lemma D.13, we do the regret decomposition firstEQUATIONEQUATION.(D.2)Next, we will bound the above three terms respectively.Bounding Term (i) in (D.2): for the policy π k m,h , we havem∈M K k=1 H h=1 E π * Q k m,h (s m,h , •), π * m,h (•, |s m,h ) -π k m,h (•|s m,h ) |s m,1 = s k m,1 ≤ 0. (D.3)This is because by definition π k m,h is the greedy policy forQ k m,h . Bounding Term (ii) in (D.2): note that 0 ≤ Q k m,h ≤ H -h + 1 ≤ H, based on (D.1), for any (m, k, h) ∈ M × [K] × [H], we have |D m,k,h,1 | ≤ 2H and |D m,k,h,2 | ≤ 2H. Note that D m,k,h,1 is a martingale difference sequence E[D m,k,h,1 |F m,k,h ] = 0.By applying Azuma-Hoeffding inequality, with probability at least 1 -δ/3, we havem∈M K k=1 H h=1 D m,k,h,1 ≤ 2 2M H 3 K log(6/δ).Note that D m,k,h,2 is also a martingale difference sequence. By applying Azuma-Hoeffding inequality, with probability at least 1 -δ/3, we havem∈M K k=1 H h=1 D m,k,h,2 ≤ 2 2M H 3 K log(6/δ).By taking union bound, with probability at least 1 -2δ/3, we havem∈M K k=1 H h=1 D m,k,h,1 + m∈M K k=1 H h=1 D m,k,h,2 ≤ 4 2M H 3 K log(6/δ). (D.4)Bounding Term (iii) in (D.2): based on Lemmas D.9 and D.10, by taking union bound, with probability at least1 -|C(ε)|c ′ 0 N -2δ ′ -M HK(δ ′ + δ ′ 2 ), we have m∈M K k=1 H h=1 E π * l k m,h (s m,h , a m,h )|s m,1 = s k m,1 -l k m,h s k m,h , a k m,h ≤ m∈M K k=1 H h=1 α δ ′ ε -l k m,h s k m,h , a k m,h ≤ HM Kα δ ′ ε + m∈M K k=1 H h=1 5H √ dC δ ′ + 5 2d log( √ N /δ ′ ) 3β K + 4 3 ϕ(s k m,h , a k m,h ) (Λ k m,h ) -1 = HM Kα δ ′ ε + 5H √ dC δ ′ + 5 2d log( √ N /δ ′ ) 3β K + 4 3 H h=1 m∈M K k=1 ϕ(s k m,h , a k m,h ) (Λ k m,h ) -1 ≤ HM Kα δ ′ ε + 5H √ dC δ ′ + 5 2d log( √ N /δ ′ ) 3β K + 4 3 × H h=1 log det(Λ K h ) det(λI) + 1 M √ γ + 2 M K log det(Λ K h ) det(λI) ≤ HM Kα δ ′ ε + 5H √ dC δ ′ + 5 2d log( √ N /δ ′ ) 3β K + 4 3 × H d(log(1 + M K/d) + 1)M √ γ + 2 M Kd log(1 + M K/d) .The first inequality follows from Lemma D.10, the second inequality follows from Lemma D.9, the third inequality follows from Lemma D.12, the last inequality holds due to Lemma J.2 and the fact that ∥ϕ(•)∥ 2 ≤ 1.Here we choose ε = dH d/M K/α δ ′ = O( 1/dHM 3 K 4 N ) and choose 1 √ β K = 20H √ dC δ ′ + 16 3 , we have m∈M K k=1 H h=1 Eπ * l k m,h (s m,h , a m,h )|sm,1 = s k m,1 -l k m,h s k m,h , a k m,h ≤ O dH 2 dM √ γ + √ dM K , (D.5)occurs with probability at least1 -|C(ε)|c ′ 0 N -2δ ′ -M HK(δ ′ + δ ′ 2 ).We set δ ′ = δ/12(M HK + 1) and choose N = C log(δ)/ log(c ′ 0 ) where C = O(d), then we have1 -|C(ε)|c ′ 0 N -2δ ′ -M HK(δ ′ + δ ′ 2 ) ≥ 1 -δ/3.Combining Terms (i)(ii)(iii) together: Based on (D. w k,j m,h = w k,j-1 m,h -η m,k ∇L k m,h w k,j-1 m,h + 2η m,k β -1 m,k ϵ k,j m,h ,where we have∇L k m,h w k,j-1 m,h = 2 Λ k m,h w k,j-1 m,h -b k m,h. Plug in the above formula, then we can calculate thatw k,J k m,h = w k,J k -1 m,h -2η m,k Λ k m,h w k,J k -1 m,h -b k m,h + 2η m,k β -1 m,k ϵ k,J k m,h = I -2η m,k Λ k m,h w k,J k -1 m,h + 2η m,k b k m,h + 2η m,k β -1 m,k ϵ k,J k m,h = I -2η m,k Λ k m,h J k w k,0 m,h + J k -1 l=0 (I -2η m,k Λ k m,h ) l 2η m,k b k m,h + 2η m,k β -1 m,k ϵ k,J k -l m,h = I -2η m,k Λ k m,h J k w k,0 m,h + 2η m,k J k -1 l=0 I -2η m,k Λ k m,h l b k m,h + 2η m,k β -1 m,k J k -1 l=0 I -2η m,k Λ k m,h l ϵ k,J k -l m,h, where the third equality follows from iteration. Denote that A i = I -2η m,i Λ i m,h . Moreover, we choose the step size such that 0 < η m,i < 1/ 2λ max Λ i m,h . Thus we havew k,J k m,h = A J k k w k-1,J k-1 m,h + 2η m,k J k -1 l=0 A l k Λ k m,h w k m,h + 2η m,k β -1 m,k J k -1 l=0 A l k ϵ k,J k -l m,h = A J k k w k-1,J k-1 m,h + (I -A k ) I + A k + ... + A J k -1 k w k m,h + 2η m,k β -1 m,k J k -1 l=0 A l k ϵ k,J k -l m,h = A J k k w k-1,J k-1 m,h + I -A J k k w k m,h + 2η m,k β -1 m,k J k -1 l=0 A l k ϵ k,J k -l m,h = A J k k ...A J1 1 w 1,0 m,h + k i=1 A J k k ...A Ji+1 i+1 I -A Ji i w i m,h + k i=1 2η m,i β -1 m,i A J k k ...A Ji+1 i+1 Ji-1 l=0 A l i ϵ i,Ji-l m,h ,where the first equality holds becauseb k m,h = Λ k m,h w k m,h and w k-1,J k-1 m,h= w k,0 m,h , the third equality follows from the fact that I + A + ...+ A n-1 = (I -A n )(I -A) -1, and the fourth equality holds because of iteration.Note that ϵ i,Ji-l m,h ∼ N (0, I), based on the property of multivariate Gaussian distribution, we havew k,J k m,h ∼ N µ k,J k m,h , Σ k,J k m,h .Then we can directly get the mean vectorµ k,J k m,h = A J k k ...A J1 1 w 1,0 m,h + k i=1 A J k k ...A Ji+1 i+1 I -A Ji i w i m,h .Next we will calculate the covariance matrix Σ k,J k m,h . For simplicity, we defineEQUATIONi+1 , thus we haveM i Ji-1 l=0 A l i ϵ i,Ji-l m,h ∼ N 0, Ji-1 l=0 M i A l i M i A l i ⊤ ∼ N 0, M i Ji-1 l=0 A 2l i M ⊤ i .Thus we get the covariance matrixΣ k,J k m,h , Σ k,J k m,h = k i=1 M i Ji-1 l=0 A 2l i M ⊤ i = k i=1 2η m,i β -1 m,i A J k k ...A Ji+1 i+1 Ji-1 l=0 A 2l i A Ji+1 i+1 ...A J k k = k i=1 2η m,i β -1 m,i A J k k ...A Ji+1 i+1 I -A 2Ji i (I -A 2 i ) -1 A Ji+1 i+1 ...A J k k = k i=1 1 β m,i A J k k ...A Ji+1 i+1 I -A 2Ji i Λ i m,h -1 (I + A i ) -1 A Ji+1 i+1 ...A J k k ,where the third equality follows from the fact that I + A + ...+ A n-1 = (I -A n )(I -A) -1 .Here we complete the proof.E.2 Proof of Lemma D.4 Proof. Note that w k m,h = Λ k m,k -1 b k m,h , we can calculate that w k m,h = Λ k m,h -1 b k m,h = Λ k m,h -1 (s l ,a l ,s ′ l )∈U m,h (k) r h s l , a l + V k m,h+1 (s ′ l ) ϕ s l , a l ≤ 1 √ λ K(k) (s l ,a l ,s ′ l )∈U m,h (k) r h s l , a l + V k m,h+1 (s ′ l ) ϕ s l , a l 2 (Λ k m,h ) -1 1/2 ≤ 2H √ λ K(k) (s l ,a l ,s ′ l )∈U m,h (k) ϕ(s l , a l ) 2 (Λ k m,h ) -1 1/2 ≤ 2H K(k)d/λ ≤ 2H M kd/λ,where the first inequality follows from Lemma J.3, the second inequality is due to 0 ≤ V k m,h ≤ H -h + 1, 0 ≤ r h ≤ 1 and ∥ϕ(s, a)∥ ≤ 1, the third inequality follows from Lemma J.4, and the last inequality holds becauseK(k) = (M -1)k s + k -1 ≤ M k. E.3 Proof of Lemma D.5Proof. We separate the error into two terms and bound them respectively,ϕ(s, a) ⊤ w k,J k m,h -ϕ(s, a) ⊤ w k m,h ≤ ϕ(s, a) ⊤ w k,J k m,h -µ k,J k m,h I1 + ϕ(s, a) ⊤ µ k,J k m,h -w k m,h I2 . (E.1)Bounding Term I 1 in (E.1): by Cauchy-Schwarz inequality, we haveϕ(s, a) ⊤ w k,J k m,h -µ k,J k m,h ≤ ϕ(s, a) Σ k,J k m,h • w k,J k m,h -µ k,J k m,h (Σ k,J k m,h ) -1 . By choosing η m,k ≤ 1/(4λ max (Λ k m,h)) for all k and m, then we have1 2 I ≼ A k = I -2η m,k Λ k m,h ≼ (1 -2η m,k λ min (Λ k m,h ))I, (E.2) 3 2 I ≼ I + A k = 2I -2η m,k Λ k m,h ≼ 2I. Recall the definition of Σ k,J k m,h in Proposition D.3. By choosing β m,i = β K for all i ∈ [k] and m ∈ M, then we have ϕ(s, a) ⊤ Σ k,J k m,h ϕ(s, a) = k i=1 1 β m,i ϕ(s, a) ⊤ A J k k ...A Ji+1 i+1 I -A 2Ji i Λ i m,h -1 (I + A i ) -1 A Ji+1 i+1 ...A J k k ϕ(s, a) ≤ 2 3β m,i k i=1 ϕ(s, a) ⊤ A J k k ...A Ji+1 i+1 Λ i m,h -1 -A Ji i Λ i m,h -1 A Ji i A Ji+1 i+1 ...A J k k ϕ(s, a) = 2 3β K k-1 i=1 ϕ(s, a) ⊤ A J k k ...A Ji+1 i+1 Λ i m,h -1 -Λ i+1 m,h -1 A Ji+1 i+1 ...A J k k ϕ(s, a) - 2 3β K ϕ(s, a) ⊤ A J k k ...A J1 1 (Λ 1 m,h ) -1 A J1 1 ...A J k k ϕ(s, a) + 2 3β K ϕ(s, a) ⊤ (Λ k m,h ) -1 ϕ(s, a),where the first inequality follows from (E.2). By the definition of Λ i m,h and Woodbury formula, we haveΛ i m,h -1 -Λ i+1 m,h -1 = Λ i m,h -1 -Λ i m,h + (s l ,a l ,s ′l )∈U m,h (k) ϕ s l , a l ϕ s l , a l ⊤ -1 = (Λ i m,h ) -1 φ(I n + φ ⊤ (Λ i m,h ) -1 φ) -1 φ ⊤ (Λ i m,h ) -1 ,where φ is a matrix with the dimension of d × n, n is the number difference of ϕ s l , a l between Λ i m,h-1 and Λ i+1 m,h -1 (i.e.we concatenate all ϕ s l , a l into the matrix φ). Note that n ≤ M , then we haveϕ(s, a) ⊤ A J k k ...A Ji+1 i+1 Λ i m,h -1 -Λ i+1 m,h -1 A Ji+1 i+1 ...A J k k ϕ(s, a) = ϕ(s, a) ⊤ A J k k ...A Ji+1 i+1 Λ i m,h -1 φ(I n + φ ⊤ Λ i m,h -1 φ) -1 φ ⊤ Λ i m,h -1 A Ji+1 i+1 ...A J k k ϕ(s, a) ≤ ϕ(s, a) ⊤ A J k k ...A Ji+1 i+1 Λ i m,h -1 φφ ⊤ Λ i m,h -1 A Ji+1 i+1 ...A J k k ϕ(s, a) = ϕ(s, a) ⊤ A J k k ...A Ji+1 i+1 Λ i m,h -1 φ 2 2 ≤ A J k k ...A Ji+1 i+1 (Λ i m,h ) -1/2 ϕ(s, a) 2 2 • (Λ i m,h ) -1/2 φ 2 F ≤ k j=i+1 1 -2η m,j λ min Λ j m,h 2Jj tr φ ⊤ Λ i m,h -1 φ ∥ϕ(s, a)∥ 2 (Λ i m,h ) -1 ,where ∥•∥ F is Frobenius norm and the last inequality is due to ∥Λ -1 2 X∥ 2 F = tr(X ⊤ Λ -1 X) and (E.2). Thus we have ϕ(s, a)2 Σ k,J k m,h ≤ 2 3βK k i=1 k j=i+1 1 -2ηm,jλmin Λ j m,h 2J j tr φ ⊤ Λ i m,h -1 φ ∥ϕ(s, a)∥ 2 (Λ i m,h ) -1 + 2 3βK ∥ϕ(s, a)∥ 2 (Λ k m,h ) -1 .Using the inequality√ a 2 + b 2 ≤ a + b for a, b > 0, we get ϕ(s, a) Σ k,J k m,h ≤ 2 3βK k i=1 k j=i+1 1 -2ηm,jλmin(Λ j m,h ) J j tr(φ ⊤ (Λ i m,h ) -1 φ) 1 2 ∥ϕ(s, a)∥ (Λ i m,h ) -1 + ∥ϕ(s, a)∥ (Λ k m,h ) -1 def = g k m,h (ϕ(s, a)). Note that Σ k,J k m,h -1/2 w k,J k m,h -µ k,J k m,h ∼ N (0, I d ).By the Gaussian concentration property, we haveP Σ k,J k m,h -1/2 w k,J k m,h -µ k,J k m,h ≥ 4d log(1/δ) ≤ δ 2 .Then we haveP ϕ(s, a) ⊤ w k,J k m,h -ϕ(s, a) ⊤ µ k,J k m,h ≥ 2 g k m,h (ϕ(s, a)) d log(1/δ) ≤ P ϕ(s, a) ⊤ w k,J k m,h -ϕ(s, a) ⊤ µ k,J k m,h ≥ 2 d log(1/δ)∥ϕ(s, a)∥ Σ k,J k m,h ≤ P ϕ(s, a) Σ k,J k m,h • w k,J k m,h -µ k,J k m,h (Σ k,J k m,h ) -1 ≥ 2 d log(1/δ)∥ϕ(s, a)∥ Σ k,J k m,h = P Σ k,J k m,h -1/2 w k,J k m,h -µ k,J k m,h ≥ 2 d log(1/δ) ≤ δ 2 . (E.3)Bounding Term I 2 in (E.1): Recall from Proposition D.3, we haveµ k,J k m,h = A J k k ...A J1 1 w 1,0 m,h + k i=1 A J k k ...A Ji+1 i+1 I -A Ji i w i m,h = A J k k ...A J1 1 w 1,0 m,h + k-1 i=1 A J k k ...A Ji+1 i+1 ( w i m,h -w i+1 m,h ) -A J k k ...A J1 1 w 1 m,h + w k m,h = A J k k ...A J1 1 (w 1,0 m,h -w 1 m,h ) + k-1 i=1 A J k k ...A Ji+1 i+1 ( w i m,h -w i+1 m,h ) + w k m,h .Then we can getϕ(s, a) ⊤ (µ k,J k m,h -w k m,h ) = ϕ(s, a) ⊤ A J k k ...A J1 1 (w 1,0 m,h -w 1 m,h ) I21 + ϕ(s, a) ⊤ k-1 i=1 A J k k ...A Ji+1 i+1 ( w i m,h -w i+1 m,h ) I22 .In Algorithm 3, we choose w 1,0 m,h = 0 and w 1 m,h = (Λ 1 m,h ) -1 b 1 m,h = 0. Thus we have I 21 = 0. To bound term I 22 , we use the inequalities in (E.2) and Lemma D.4, we haveI 22 ≤ k-1 i=1 ϕ(s, a) ⊤ A J k k ...A Ji+1 i+1 ( w i m,h -w i+1 m,h ) ≤ k-1 i=1 k j=i+1 1 -2η m,j λ min (Λ j m,h ) Jj ∥ϕ(s, a)∥(∥ w i m,h ∥ + ∥ w i+1 m,h ∥) ≤ k-1 i=1 k j=i+1 1 -2η m,j λ min (Λ j m,h ) Jj ∥ϕ(s, a)∥ 2H M id/λ + 2H M (i + 1)d/λ ≤ 4H M Kd/λ k-1 i=1 k j=i+1 1 -2η m,j λ min (Λ j m,h ) Jj ∥ϕ(s, a)∥.Thus we getϕ(s, a) ⊤ µ k,J k m,h -w k m,h ≤ 4H M Kd/λ k-1 i=1 k j=i+1 1 -2η m,j λ min (Λ j m,h ) Jj ∥ϕ(s, a)∥. (E.4)Substituting (E.3) and (E.4) into (E.1), with probability at least 1 -δ 2 , we haveϕ(s, a) ⊤ w k,J k m,h -ϕ(s, a) ⊤ w k m,h ≤ 4H M Kd/λ k-1 i=1 k j=i+1 1 -2ηm,jλmin(Λ j m,h ) J j ∥ϕ(s, a)∥ + 2 2d log(1/δ) 3βK ∥ϕ(s, a)∥ (Λ k m,h ) -1 + 2 2d log(1/δ) 3βK k i=1 k j=i+1 1 -2ηm,jλmin(Λ j m,h ) J j tr φ ⊤ Λ i m,h -1 φ 1 2 ∥ϕ(s, a)∥ (Λ i m,h ) -1 def = W. (E.5)Here we choose η m,j = 1/(4λ max (Λ j m,h )) and set κ j = λ max Λ j m,h /λ min Λ j m,h , then we have1 -2η m,j λ min Λ j m,h Jj = (1 -1/2κ j ) Jj .We want to have (1 -1/2κ j ) Jj < ϵ, it suffices to choose J j such thatJ j ≥ log(1/ϵ) log 1 1-1/2κj. Note that 1/2κ j ≤ 1/2, we have log(1/(1 -1/2κ j )) ≥ 1/2κ j because e -x > 1 -x for 0 < x < 1. Therefore, we only need to pick J j ≥ 2κ j log(1/ϵ).Also note that 1 ≥ ∥ϕ(s, a)∥ ≥ √ λ∥ϕ(s, a)∥ (Λ i m,h ) -1 and tr φ ⊤ Λ i m,h-1 φ ≤ M due to the fact that n ≤ M . By setting ϵ = 1/(4HM Kd) and λ = 1, we obtainW ≤ k-1 i=1 ϵ k-i 4H M Kd/λ∥ϕ(s, a)∥ + 2 2d log(1/δ) 3βK ∥ϕ(s, a)∥ (Λ k m,h ) -1 + k-1 i=1 ϵ k-i √ M ∥ϕ(s, a)∥ ≤ k-1 i=1 ϵ k-i 4H M Kd/λ √ M K∥ϕ(s, a)∥ (Λ k m,h ) -1 + 2 2d log(1/δ) 3βK ∥ϕ(s, a)∥ (Λ k m,h ) -1 + k-1 i=1 ϵ k-i M √ K∥ϕ(s, a)∥ (Λ k m,h ) -1 ≤ k-1 i=1 ϵ k-i-1 ∥ϕ(s, a)∥ (Λ k m,h ) -1 + 2 2d log(1/δ) 3βK ∥ϕ(s, a)∥ (Λ k m,h ) -1 + k-1 i=1 ϵ k-i-1 ∥ϕ(s, a)∥ (Λ k m,h ) -1 ≤ 5 2d log(1/δ) 3βK + 4 3 ∥ϕ(s, a)∥ (Λ k m,h ) -1 ,where the second inequality follows from ∥ϕ(s, a)∥ (Λ k m,h ) -1 ≥ 1/ K(k) + 1∥ϕ(s, a)∥ ≥ 1/ √ M K∥ϕ(s, a)∥, the fourth inequality follows from k-1 i=1 ϵ k-i-1 = k-2 i=0 ϵ i < 1/(1-ϵ) ≤ 4/3. Finally we have P ϕ(s, a) ⊤ w k,J k m,h -ϕ(s, a) ⊤ w k m,h ≤ 5 2d log(1/δ) 3β K + 4 3 ∥ϕ(s, a)∥ (Λ k m,h ) -1 ≥ P ϕ(s, a) ⊤ w k,J k m,h -ϕ(s, a) ⊤ w k m,h ≤ W ≥ 1 -δ 2 .This completes the proof.E.4 Proof of Lemma D.6 Proof. Recall that w k,J k m,h ∼ N µ k,J k m,h , Σ k,J k m,h . Let ξ k,J k m,h = w k,J k m,h -µ k,J k m,h ∼ N (0, Σ k,J k m,h ), thus we have w k,J k m,h = µ k,J k m,h + ξ k,J k m,h ≤ µ k,J k m,h + ξ k,J k m,h . (E.6) Bounding µ k,J k m,h in (E.6): Based on Proposition D.3, we have µ k,J k m,h = A J k k . . . A J1 1 w 1,0 m,h + k i=1 A J k k . . . A Ji+1 i+1 I -A Ji i w i m,h ≤ k i=1 A J k k . . . A Ji+1 i+1 I -A Ji i F • w i m,h ≤ 2H M Kd/λ k i=1 A J k k . . . A Ji+1 i+1 I -A Ji i F ≤ 2Hd M K/λ k i=1 ∥A k ∥ J k 2 . . . ∥A i+1 ∥ Ji+1 2 I -A Ji i 2 ≤ 2Hd M K/λ k i=1 k j=i+1 1 -2η m,j λ min Λ j m,h Jj ∥I∥ 2 + A i Ji 2 ≤ 2Hd M K/λ k i=1 k j=i+1 1 -2η m,j λ min Λ j m,h Jj 1 + 1 -2η m,i λ min Λ i m,h Jj ,where the second inequality holds from Lemma D.4, the third inequality follows from the fact that rankA J k k . . . A Ji+1 i+1 I -A Ji i ≤ d and ∥X∥ 2 ≤ ∥X∥ F ≤ rank(X)∥X∥ 2 where ∥X∥ 2 = σ max (X).Recall that in Lemma D.5, we set J j ≥ 2κ j log(1/ϵ) where κ j = λ max Λ j m,h /λ min Λ j m,h , ϵ = 1/(4HM Kd) and λ = 1, thus we getµ k,J k m,h ≤ 2Hd M K/λ k i=1 (ϵ k-i + ϵ k-i+1 ) ≤ 4Hd M K/λ ∞ i=0 ϵ i ≤ 16 3 Hd √ M K. Bounding ξ k,J k m,hin (E.6): Note that ξ k,J k m,h ∼ N 0, Σ k,J k m,h , using Gaussian concentration Lemma J.5, we haveP ξ k,J k m,h ≤ 1 δ tr Σ k,J k m,h ≥ 1 -δ.Recall from Proposition D.3, we havetr Σ k,J k m,h = k i=1 1 β m,i tr A J k k . . . A Ji+1 i+1 I -A 2Ji i (Λ i m,h ) -1 (I + A i ) -1 A Ji+1 i+1 . . . A J k k ≤ k i=1 1 β m,i tr A J k k . . . tr A Ji+1 i+1 tr I -A 2Ji i tr Λ i m,h -1 tr I + A i ) -1 × tr A Ji+1 i+1 . . . tr A J k k ,where the inequality holds due to Lemma J.6. Recall from (E.2) that, when η m,k ≤ 1/(4λ max (Λ k m,h )) for all k and m, we haveA Ji i ≼ (1 -2η m,k λ min (Λ k m,h )) Jj I, set λ = 1, then we obtain tr(A Ji i ) ≤ tr 1 -2η m,k λ min Λ k m,h Jj I ≤ d 1 -2η m,k λ min Λ k m,h Jj ≤ dϵ ≤ 1.Similarly, we haveI -A 2Ji i ≼ 1 -1 2 2J i I, then we get tr(I -A 2Ji i ) ≤ 1 - 1 2 2Ji d < d.A i ) -1 ≼ 23 I, we havetr (I + A i ) -1 ≤ 2 3 d. Note that λ max Λ i m,h -1 ≤ 1, we have tr Λ i m,h -1 ≤ λ Λ i m,h -1 ≤ d.Combine the above results together and choose β m,i = β K for all i ∈ [K] and m ∈ M, we havetr Σ k,J k m,h ≤ K i=1 1 β m,i • 2 3 • d 3 = 2 3β K Kd 3 .Then we haveP ξ k,J k m,h ≤ 1 δ • 2 3β K Kd 3 ≥ P ξ k,J k m,h ≤ 1 δ tr Σ k,J k m,h ≥ 1 -δ.Combine above results together: with probability at least 1 -δ, we havew k,J k m,h ≤ 16 3 Hd √ M K + 2K 3β K δ d 3/2 .This completes the proof.E.5 Proof of Lemma D.7Proof. Based on Lemma D.6, for any fixed n ∈ [N ], with probability at least 1 -δ, for any(m, k, h) ∈ M × [K] × [H],we havew k,J k ,n m,h ≤ 16 3 Hd √ M K + 2K 3β K δ d 3/2 .By taking union over n, m, k, h, we have for all(m, k, h) ∈ M × [K] × [H] and for all n ∈ [N ],with probability 1 -δ/2, we havew k,J k ,n m,h ≤ 16 3 Hd √ M K + 4N M HK 2 3β K δ d 3/2 = B δ/2N M HK . (E.7)Based on Lemma J.7 and Lemma J.9, we have that for any ε > 0 and δ > 0, with probability at least1 -δ/2, (s l ,a l ,s ′ l )∈U m,h (k) ϕ s l , a l V k m,h+1 -P h V k m,h+1 s l , a l (Λ k m,h ) -1 ≤ 4H 2 d 2 log k + λ λ + d log B δ/2N M HK ε + log 3 δ + 8k 2 ε 2 λ 1/2 ≤ 2H d 2 log k + λ λ + d log B δ/2N M HK ε + log 3 δ 1/2 + 2 √ 2kε √ λ .Here we set λ = 1, ε = H 2 √ 2k , with probability at least 1 -δ/2, we have(s l ,a l ,s ′ l )∈U m,h (k) ϕ s l , a l V k m,h+1 -P h V k m,h+1 s l , a l (Λ k m,h ) -1 ≤ 2H √ d 1 2 log(k + 1) + log B δ/2N M HK H 2 √ 2k + log 3 δ 1/2 + H ≤ 3H √ d 1 2 log(K + 1) + log 2 √ 2KB δ/2N M HK H + log 3 δ 1/2 . (E.8)By applying union bound between (E.7) and (E.8), and define thatC δ = 1 2 log(K + 1) + log 3 δ + log 2 √ 2KB δ/2N M HK H 1/2, finally we obtain that for all (m, k, h)∈ M × [K] × [H], (s l ,a l ,s ′ l )∈U m,h (k) ϕ s l , a l V k m,h+1 -P h V k m,h+1 s l , a l (Λ k m,h ) -1 ≤ 3H √ dC δ ,with probability at least 1 -δ.Proof. We denote the inner product over S by ⟨•, •⟩ S . Based on P h (•|s, a) = ϕ(s, a), µ h (•) S in Definition 4.1, we haveP h V k m,h+1 (s, a) = ϕ(s, a) ⊤ µ h , V k m,h+1 S = ϕ(s, a) ⊤ Λ k m,h -1 Λ k m,h µ h , V k m,h+1 S = ϕ(s, a) ⊤ Λ k m,h -1 (s l ,a l ,s ′l )∈U m,h (k) ϕ s l , a l ϕ s l , a l ⊤ + λI µ h , V k m,h+1 S = ϕ(s, a) ⊤ Λ k m,h -1 (s l ,a l ,s ′l )∈U m,h (k) ϕ s l , a l P h V k m,h+1 s l , a l + λI µ h , V k m,h+1 S .(E.9)Here the last equality uses P h (•|s, a) = ϕ(s, a), µ h (•) S again. Then we can separate the following error into three parts,ϕ(s, a) ⊤ w k m,h -r h (s, a) -P h V k m,h+1 (s, a) = ϕ(s, a) ⊤ Λ k m,h -1 (s l ,a l ,s ′l )∈U m,h (k) r h s l , a l + V k m,h+1 (s ′ l ) ϕ s l , a l -r h (s, a) -ϕ(s, a) ⊤ Λ k m,h -1 (s l ,a l ,s ′ l )∈U m,h (k) ϕ s l , a l P h V k m,h+1 s l , a l + λI µ h , V k m,h+1 S = ϕ(s, a) ⊤ Λ k m,h -1 (s l ,a l ,s ′l )∈U m,h (k) ϕ s l , a l V k m,h+1 -P h V k m,h+1 s l , a l (i) + ϕ(s, a) ⊤ Λ k m,h -1 (s l ,a l ,s ′ l )∈U m,h (k)r h s l , a l ϕ s l , a l -r h (s, a)EQUATION.(E.10)Here the first equality holds due to (E.9). We now provide an upper bound for each of the terms in (E.10).Bounding Term (i) in (E.10): using Cauchy-Schwarz inequality and Lemma D.7, with probability at least 1 -δ, for all (m, k, h) ∈ M × [K] × [H] and for any (s, a) ∈ S × A, we haveϕ(s, a) ⊤ Λ k m,h -1 (s l ,a l ,s ′ l )∈U m,h (k) ϕ s l , a l V k m,h+1 -P h V k m,h+1 s l , a l ≤ (s l ,a l ,s ′ l )∈U m,h (k) ϕ s l , a l V k m,h+1 -P h V k m,h+1 s l , a l (Λ k m,h ) -1 ∥ϕ(s, a)∥ (Λ k m,h ) -1 ≤ 3H √ dC δ ∥ϕ(s, a)∥ (Λ k m,h ) -1 . (E.11)Bounding Term (ii) in (E.10): we first note thatϕ(s, a) ⊤ Λ k m,h -1 (s l ,a l ,s ′ l )∈U m,h (k) r h s l , a l ϕ s l , a l -r h (s, a) = ϕ(s, a) ⊤ Λ k m,h -1 (s l ,a l ,s ′ l )∈U m,h (k) r h s l , a l ϕ s l , a l -ϕ(s, a) ⊤ θ h = ϕ(s, a) ⊤ Λ k m,h -1 (s l ,a l ,s ′ l )∈U m,h (k) r h s l , a l ϕ s l , a l -Λ k m,h θ h = ϕ(s, a) ⊤ Λ k m,h -1 (s l ,a l ,s ′ l )∈U m,h (k) r h s l , a l ϕ s l , a l - (s l ,a l ,s ′ l )∈U m,h (k) ϕ s l , a l ϕ s l , a l ⊤ θ h -λIθ h = ϕ(s, a) ⊤ Λ k m,h -1 (s l ,a l ,s ′ l )∈U m,h (k) r h s l , a l ϕ s l , a l - (s l ,a l ,s ′ l )∈U m,h (k) ϕ s l , a l r h s l , a l -λθ h = -λϕ(s, a) ⊤ Λ k m,h -1 θ h , (E.12)where the first and fourth equality holds due to the definition r h (s, a) = ϕ(s, a), θ h from Definition 4.1, the third equality uses the definition of Λ k m,h . Next we can obtain that-λϕ(s, a) ⊤ Λ k m,h -1 θ h ≤ λ∥ϕ(s, a)∥ (Λ k m,h ) -1 ∥θ h ∥ (Λ k m,h ) -1 ≤ √ λ∥ϕ(s, a)∥ (Λ k m,h ) -1 ∥θ h ∥ ≤ √ λd∥ϕ(s, a)∥ (Λ k m,h ) -1 , (E.13)where we use the fact that λ max Λ k m,h -1 ≤ 1/λ and ∥θ h ∥ ≤ √ d from Definition 4.1. By Combining (E.12) and (E.13), we obtainϕ(s, a) ⊤ Λ k m,h -1 (s l ,a l ,s ′ l )∈U m,h (k) r h s l , a l ϕ s l , a l -r h (s, a) ≤ √ λd∥ϕ(s, a)∥ (Λ k m,h ) -1 . (E.14)Bounding Term (iii) in (E.10): we haveλϕ(s, a) ⊤ Λ k m,h -1 µ h , V k m,h+1 S ≤ λ∥ϕ(s, a)∥ (Λ k m,h ) -1 µ h , V k m,h+1 S (Λ k m,h ) -1 ≤ √ λ∥ϕ(s, a)∥ (Λ k m,h ) -1 µ h , V k m,h+1 S ≤ H √ λ∥ϕ(s, a)∥ (Λ k m,h ) -1 ∥µ h ∥ ≤ H √ λd∥ϕ(s, a)∥ (Λ k m,h ) -1 , (E.15)where the second inequality holds due to the fact that λ max Λ k m,h -1 ≤ 1/λ, the third inequality uses the fact that V k m,h+1 ≤ H and the last inequality follows from ∥µ h ∥ ≤ √ d in Definition 4.1.Combine Terms (i)(ii)(iii) together: combine (E.11), (E.14) and (E.15), then set λ = 1, with probability at least 1 -δ, we getϕ(s, a) ⊤ w k m,h -r h (s, a) -P h V k m,h+1 (s, a) ≤ 3HC δ + √ λd + H √ λd ∥ϕ(s, a)∥ (Λ k m,h ) -1 ≤ 5H √ dC δ ∥ϕ(s, a)∥ (Λ k m,h ) -1 , This completes the proof. E.7 Proof of Lemma D.9 Proof. Recall from Definition D.1, -l k m,h (s, a) = Q k m,h (s, a) -r h (s, a) -P h V k m,h+1 (s, a) = min max n∈[N ] ϕ(s, a) ⊤ w k,J k ,n m,h , H -h + 1 + -r h (s, a) -P h V k m,h+1 (s, a) ≤ max n∈[N ] ϕ(s, a) ⊤ w k,J k ,n m,h -r h (s, a) -P h V k m,h+1 (s, a) = max n∈[N ] ϕ(s, a) ⊤ w k,J k ,n m,h -ϕ(s, a) ⊤ w k m,h + ϕ(s, a) ⊤ w k m,h -r h (s, a) -P h V k m,h+1 (s, a) ≤ max n∈[N ] ϕ(s, a) ⊤ w k,J k ,n m,h -ϕ(s, a) ⊤ w k m,h I1 + ϕ(s, a) ⊤ w k m,h -r h (s, a) -P h V k m,h+1 (s, a) I2 .Bounding Term I 1 : based on Lemma D.5, for any fixed n ∈ [N ], for any (m, h, k) ∈ M×[H]×[K] and for any (s, a) ∈ S × A, with probability at least 1 -δ 2 , we haveϕ(s, a) ⊤ w k,J k ,n m,h -ϕ(s, a) ⊤ w k m,h ≤ 5 2d log(1/δ) 3β K + 4 3 ∥ϕ(s, a)∥ (Λ k m,h ) -1 .By taking union bound over n, we have for all n ∈ [N ], with probability 1 -δ 2 , we haveϕ(s, a) ⊤ w k,J k ,n m,h -ϕ(s, a) ⊤ w k m,h ≤ 5 2d log √ N /δ 3β K + 4 3 ∥ϕ(s, a)∥ (Λ k m,h ) -1 .This indicates, for any (m, h, k) ∈ M × [H] × [K] and (s, a) ∈ S × A, with probability at least 1 -δ 2 , we haveTerm I 1 = max n∈[N ] ϕ(s, a) ⊤ w k,J k ,n m,h -ϕ(s, a) ⊤ w k m,h ≤ 5 2d log √ N /δ 3β K + 4 3 ∥ϕ(s, a)∥ (Λ k m,h ) -1 . (E.16)Bounding Term I 2 : based on Lemma D.8, with probability at least 1 -δ, for any(m, h, k) ∈ M × [H] × [K] and (s, a) ∈ S × A, we have ϕ(s, a) ⊤ w k m,h -r k h (s, a) -P h V k m,h+1 (s, a) ≤ 5H √ dC δ ∥ϕ(s, a)∥ (Λ k m,h ) -1 .Combine the two result above, by taking union bound, with probability at least 1 -δ -δ 2 , for any(m, h, k) ∈ M × [H] × [K] and (s, a) ∈ S × A, we have -l k m,h (s, a) ≤ 5H √ dC δ + 5 2d log √ N /δ 3β K + 4 3 ∥ϕ(s, a)∥ (Λ k m,h ) -1 .This completes the proof.Proof. Recall from Definition D.1,l k m,h (s, a) = r h (s, a) + P h V k m,h+1 (s, a) -Q k m,h (s, a). Note that Q k m,h (s, a) = min max n∈[N ] ϕ(s, a) ⊤ w k,J k ,n m,h , H -h + 1 + ≤ max n∈[N ] ϕ(x, a) ⊤ w k,J k ,n m,h . Note that ∥ϕ(s, a)∥ (Λ k m,h ) -1 ≤ 1/λ∥ϕ(s, a)∥ ≤ 1 for all ϕ(s, a). Define C(ε) to be a ε-cover of ϕ | ∥ϕ∥ (Λ k m,h ) -1 ≤ 1 . Based on Lemma J.8, we have |C(ε)| ≤ (3/ε) d . First, for any fixed ϕ(s, a) ∈ C(ε), based on the results in Proposition D.3, we have that ϕ(s, a) ⊤ w k,J k ,n m,h ∼ N ϕ(s, a) ⊤ µ k,J k m,h , ϕ(s, a) ⊤ Σ k,J k m,h ϕ(s, a) for any fixed n ∈ [N ]. Now we define Z k = r h (s, a) + P h V k m,h+1 (s, a) -ϕ(s, a) ⊤ µ k,J k m,h ϕ(s, a) ⊤ Σ k,J k m,h ϕ(s, a).When |Z k | < 1, by Gaussian concentration Lemma J.10, we haveP ϕ(s, a) ⊤ w k,J k ,n m,h ≥ r h (s, a) + P h V k m,h+1 (s, a) = P ϕ(s, a) ⊤ w k,J k ,n m,h -ϕ(s, a) ⊤ µ k,J k m,h ϕ(s, a) ⊤ Σ k,J k m,h ϕ(s, a) ≥ r h (s, a) + P h V k m,h+1 (s, a) -ϕ(s, a) ⊤ µ k,J k m,h ϕ(s, a) ⊤ Σ k,J k m,h ϕ(s, a) = P ϕ(s, a) ⊤ w k,J k ,n m,h -ϕ(s, a) ⊤ µ k,J k m,h ϕ(s, a) ⊤ Σ k,J k m,h ϕ(s, a) ≥ Z k ≥ 1 2 √ 2π exp(-Z 2 k /2) ≥ 1 2 √ 2eπ .Consider the numerator of Z k :r h (s, a) + P h V k m,h+1 (s, a) -ϕ(s, a) ⊤ µ k,J k m,h ≤ r h (s, a) + P h V k m,h+1 (s, a) -ϕ(s, a) ⊤ w k m,h + ϕ(s, a) ⊤ w k m,h -ϕ(s, a) ⊤ µ k,J k m,h .Based on Lemma D.8, with probablity at least 1 -δ, we have|r h (s, a) + P h V k m,h+1 (s, a) -ϕ(s, a) ⊤ w k m,h | ≤ 5H √ dC δ ∥ϕ(s, a)∥ (Λ k m,h ) -1 , From (E.4), we have ϕ(s, a) ⊤ µ k,J k m,h -w k m,h ≤ 4H M Kd/λ k-1 i=1 k j=i+1 1 -2η m,j λ min (Λ j m,h ) Jj ∥ϕ(s, a)∥.Recall the proof of Lemma D.5, we set η m,j = 1/(4λ max (Λ j m,h )), J j ≥ 2κ j log(1/ϵ), then we have for all j ∈ [K], (1 -2η m,j λ min (Λ j m,h )) Jj ≤ ϵ, set ϵ = 1/4HM Kd and λ = 1, we haveϕ(s, a) ⊤ w k m,h -ϕ(s, a) ⊤ µ k,J k m,h ≤ 4H √ M Kd k-1 i=1 ϵ k-i ∥ϕ(s, a)∥ ≤ k-1 i=1 ϵ k-i-1 1 4M HKd 4H √ M Kd √ M K∥ϕ(s, a)∥ (Λ k m,h ) -1 ≤ 4 3 ∥ϕ(s, a)∥ (Λ k m,h ) -1. So, with probablity at least 1 -δ, we haver h (s, a) + P h V k m,h+1 (s, a) -ϕ(s, a) ⊤ µ k,J k m,h ≤ 5H √ dC δ + 4 3 ∥ϕ(s, a)∥ (Λ k m,h ) -1 . (E.17)Consider the denominator of Z k : recall from the definition of Σ k,J k m,h from Proposition D.3, then we haveϕ(s, a) ⊤ Σ k,J k m,h ϕ(s, a) = k i=1 1 βm,i ϕ(s, a) ⊤ A J k k . . . A J i+1 i+1 I -A 2J i Λ i m,h -1 (I + Ai) -1 A J i+1 i+1 . . . A J k k ϕ(s, a) ≥ k i=1 1 2βm,i ϕ(s, a) ⊤ A J k k . . . A J i+1 i+1 I -A 2J i Λ i m,h -1 A J i+1 i+1 . . . A J k k ϕ(s, a),where we used the fact that 1 2 I ≼ (I + A k ) -1 . Then we haveϕ(s, a) ⊤ Σ k,J k m,h ϕ(s, a) ≥ k i=1 1 2βm,i ϕ(s, a) ⊤ A J k k . . . A J i+1 i+1 Λ i m,h -1 -A J i i Λ i m,h -1 A J i i A J i+1 i+1 . . . A J k k ϕ(s, a) = 1 2βK k-1 i=1 ϕ(s, a) ⊤ A k k . . . A J i+1 i+1 Λ i m,h -1 -Λ i+1 m,h -1 A J i+1 i+1 . . . A J k k ϕ(s, a) - 1 2βK ϕ(s, a) ⊤ A J k k . . . A J 1 1 Λ 1 m,h -1 A J 1 1 . . . A J k k ϕ(s, a) + 1 2βK ϕ(s, a) ⊤ Λ k m,h -1 ϕ(s, a).By the definition of Λ i m,h and Woodbury formula, we haveΛ i m,h -1 -Λ i+1 m,h -1 = Λ i m,h -1 -Λ i m,h + (s l ,a l ,s ′l )∈U m,h (k) ϕ s l , a l ϕ s l , a l ⊤ -1 = (Λ i m,h ) -1 φ I n + φ ⊤ (Λ i m,h ) -1 φ -1 φ ⊤ (Λ i m,h ) -1, where φ is a matrix with the dimension of d × n, n is the number difference of ϕ s l , a l between Λ i m,h -1 and Λ i+1 m,h -1 (i.e. we concatenate all ϕ s l , a l in to the matrix φ). Note that n ≤ M , we haveϕ(s, a) ⊤ A J k k ...A Ji+1 i+1 Λ i m,h -1 -Λ i+1 m,h -1 A Ji+1 i+1 ...A J k k ϕ(s, a) = ϕ(s, a) ⊤ A J k k ...A Ji+1 i+1 Λ i m,h -1 φ(I n + φ ⊤ Λ i m,h -1 φ) -1 φ ⊤ Λ i m,h -1 A Ji+1 i+1 ...A J k k ϕ(s, a) ≤ ϕ(s, a) ⊤ A J k k ...A Ji+1 i+1 Λ i m,h -1 φφ ⊤ Λ i m,h -1 A Ji+1 i+1 ...A J k k ϕ(s, a) = ϕ(s, a) ⊤ A J k k ...A Ji+1 i+1 Λ i m,h -1 φ 2 2 ≤ A J k k ...A Ji+1 i+1 (Λ i m,h ) -1/2 ϕ(s, a) 2 2 • (Λ i m,h ) -1/2 φ 2 F ≤ k j=i+1 1 -2η m,j λ min Λ j m,h 2Jj tr φ ⊤ Λ i m,h -1 φ ∥ϕ(s, a)∥ 2 (Λ i m,h ) -1 ,where ∥•∥ F is Frobenius norm and the last inequality is due to ∥Λ -1 2 X∥ 2 F = tr(X ⊤ Λ -1 X) and (E.2). Therefore, we haveϕ(s, a) ⊤ Σ k,J k m,h ϕ(s, a) ≥ 1 2β K ∥ϕ(s, a)∥ 2 (Λ k m,h ) -1 - 1 2β K k i=1 1 -2η m,i λ min Λ i m,h 2Ji ∥ϕ(s, a)∥ 2 (Λ 1 m,h ) -1 - 1 2β K k-1 i=1 k j=i+1 1 -2η m,j λ min Λ j m,h 2Jj tr φ ⊤ Λ i m,h -1 φ ∥ϕ(s, a)∥ 2 (Λ i m,h ) -1 .Similar to the proof of Lemma D.5, note that tr φ ⊤ (Λ i m,h ) -1 φ ≤ M , when we choose J j ≥ 2κ j log(3kM ), we have∥ϕ(s, a)∥ Σ k,J k m,h ≥ 1 2 √ β K ∥ϕ(s, a)∥ (Λ k m,h ) -1 - ∥ϕ(s, a)∥ (3KM ) k - k-1 i=1 √ M (3kM ) k-i ∥ϕ(s, a)∥ ≥ 1 2 √ β K ∥ϕ(s, a)∥ (Λ k m,h ) -1 - 1 3 √ kM ∥ϕ(s, a)∥ - 1 6 √ kM ∥ϕ(s, a)∥ ≥ 1 4 √ β K ∥ϕ(s, a)∥ (Λ k m,h ) -1 , (E.18)where we used the fact that λ min Λ k m,h-1 ≥ 1/kM and ∥ϕ(s, a)∥ (Λ k m,h ) -1 ≥ 1/√ kM ∥ϕ(s, a)∥. Therefore, according to (E.17) and (E. 18) , with probablity at least 1 -δ, it holds that 16 3 . Till now we have proved that for any fixed ϕ(s, a) ∈ C(ε) and for all (m, h, k)|Z k | = r h (s, a) + P h V k m,h+1 (s, a) -ϕ(s, a) ⊤ µ k,J k m,h ϕ(s, a) ⊤ Σ k,J k m,h ϕ(s, a) ≤ 5H √ dC δ + 4 3 1 4 √ β K which implies |Z k | < 1 when 1 √ β K = 20H √ dC δ +∈ M × [H] × [K],for any fixed n ∈ [N ], with probablity at least 1 -δ, we haveP ϕ(s, a) ⊤ w k,J k ,n m,h -r h (s, a) -P h V k m,h+1 (s, a) ≥ 0 ≥ 1 2 √ 2eπ .By taking union bound over n ∈ [N ], with probablity at least 1 -δ, we haveP max n∈[N ] ϕ(s, a) ⊤ w k,J k ,n m,h -r h (s, a) -P h V k m,h+1 (s, a) ≥ 0 ≥ 1 -1 - 1 2 √ 2eπ N = 1 -c ′ 0 N , where c ′ 0 = 1-1 2 √2eπ . Therefore, for any fixed ϕ(s, a) ∈ C(ε) and for all (m, h, k)∈ M×[H]×[K], with probability at least (1 -δ) 1 -c ′ 0 N > 1 -δ -c ′ 0 N , we have max n∈[N ] ϕ(s, a) ⊤ w k,J k ,n m,h -r h (s, a) -P h V k m,h+1 (s, a) ≥ 0. (E.19)Next for any ϕ = ϕ(s, a), we can findϕ ′ ∈ C(ε) such that ∥ϕ -ϕ ′ ∥ (Λ k m,h ) -1 ≤ ε. We define ∆ϕ = ϕ -ϕ ′ . Recall from Definition 4.1, we have r h (s, a) + P h V k m,h+1 (s, a) = ϕ(s, a) ⊤ θ h + ϕ(s, a) ⊤ µ h , V k m,h+1 S def = ϕ(s, a) ⊤ w k m,h , where w k m,h = θ h + µ h , V k m,h+1 S . Note that max{∥µ h (S)∥, ∥θ h ∥} ≤ √ d and V k m,h+1 ≤ H -h ≤ H, thus we have w k m,h ≤ ∥θ h ∥ + µ h , V k m,h+1 S ≤ √ d + H √ d ≤ 2H √ d.Then we define the regression error ∆w k m,h = w k m,h -w k,J k ,n m,h . Thus we havemax n∈[N ] ϕ(s, a) ⊤ w k,J k ,n m,h -r h (s, a) -P h V k m,h+1 (s, a) = max n∈[N ] -ϕ(s, a) ⊤ ∆w k m,h .Then by Cauchy-Schwarz inequality, we haveϕ ⊤ ∆w k m,h = ϕ ′ ⊤ ∆w k m,h + ∆ϕ ⊤ ∆w k m,h ≥ ϕ ′ ⊤ ∆w k m,h -∥∆ϕ∥ • ∆w k m,h ≥ ϕ ′ ⊤ ∆w k m,h - √ M Kε ∆w k m,h. By triangle inequality, with probability at least 1 -δ, we have∆w k m,h ≤ w k m,h + w k,J k ,n m,h ≤ 2H √ d + B δ/N M HK Denote α δ = √ M K 2H √ d + B δ/N M HK . Then, for all (m, h, k) ∈ M × [H] × [K], with probability at least 1 -δ, we havemax n∈[N ] ϕ ⊤ ∆w k m,h ≥ max n∈[N ] ϕ ′ ⊤ ∆w k m,h -α δ ε.Recall from (E. 19) , by taking union bound, with probability at least1 -|C(ε)|c ′ 0 N -2δ, for all (m, h, k) ∈ M × [H] × [K]and for all (s, a) ∈ S × A, we havemax n∈[N ] ϕ ⊤ ∆w k m,h ≥ -α δ ε.Finally, with probability at least1 -|C(ε)|c ′ 0 N -2δ, for all (m, h, k) ∈ M × [H] × [K]and for all (s, a) ∈ S × A, we havel k m,h (s, a) ≤ α δ ε.This completes the proof.Proof. For simplicity, we denote (s k m,h , a k m,h ) as z k m,h . we consider the following mappings(ν M , ν K ) : [M K] → [M ] × [K], ν M (τ ) = τ (modM ), ν K = τ M ,where we set ν M (τ ) = M if M |τ . Next, for any τ ≥ 0, we defineΛτ h = λI + τ M u=1 ϕ z ν K (u) ν M (u),h ϕ z ν K (u) ν M (u),h ⊤, for τ > 0, Λ0 h = λI, for τ = 0. We denote σ = {σ 1 , . . . , σ n } as the synchronization episodes, where σ i ∈ [K], we also denote σ 0 = 0. Then we separate the episodes k = 1, . . . , K into two groups based on the following condition,1 ≤ det( Λσi h ) det( Λσi-1 h ) ≤ 3. (E.20)Note that the left inequality always holds due to Λσi-1 h ≼ Λσi h and the trivial fact that A ≼ B ⇒ det(A) ≤ det(B). Then we define thatI 1 = {k ∈ N + , k ∈ [σ i-1 , σ i ), ∀i ∈ [n]|(E.20) is true} and I 2 = {k ∈ N + , k ∈ [σ i-1 , σ i ), ∀i ∈ [n]|(E.20) is false}, then [K] = I 1 ∪ I 2 ∪ {K}. For any k ∈ [σ i-1 , σ i ) and k ∈ I 1 , note that Λσi-1 h ≼ Λ k m,h ≼ Λk h ≼ Λσi h , thus for any m ∈ M, we have ϕ z k m,h (Λ k m,h ) -1 ≤ ϕ z k m,h ( Λk h ) -1 det( Λk h ) det(Λ k m,h ) ≤ ϕ z k m,h ( Λk h ) -1 det( Λσi h ) det( Λσi-1 h ) ≤ 2 ϕ z k m,h ( Λk h ) -1 , (E.21)where the first inequality follows from Lemma J.12, the second inequality follows from the trivial fact that A ≼ B ⇒ det(A) ≤ det(B), and the final inequality holds because k ∈ I 1 . Then we will bound the summation for k ∈ I 1 and k ∈ I 2 respectively.k∈I1∪{K} m∈M ∥ϕ(z k m,h )∥ (Λ k m,h ) -1 ≤ M K m∈M k∈I1∪{K} ∥ϕ(z k m,h )∥ 2 (Λ k m,h ) -1 ≤ 2 M K m∈M k∈I1∪{K} ∥ϕ(z k m,h )∥ 2 ( Λk h ) -1 ≤ 2 M K m∈M K k=1 ∥ϕ(z k m,h )∥ 2 ( Λk h ) -1 ≤ 2 M K log det(Λ K h ) det(λI),where the first inequality follows from Cauchy-Schwarz inequality, the second inequality holds due to (E.21), the final equality follows from Lemma J.1 andΛ K h = m∈M K k=1 ϕ s k m,h , a k m,h ϕ s k m,h , a k m,h ⊤ + λI. For any interval [σ i-1 , σ i ), define ∆ i = σ i -σ i-1 -1, we calculate that σi-1 k=σi-1 ϕ(z k m,h ) (Λ k m,h ) -1 ≤ ∆ i σi-1 k=σi-1 ϕ(z k m,h ) 2 (Λ k m,h ) -1 ≤ ∆ i log det(Λ σi-1 m,h ) det(Λ σi-1 m,h ) ≤ √ γ,where the last inequality follows from the synchronization (3.3).Define R h = logdet(Λ K h ) det(λI), note that σ n ≤ K, then we can find thatR h ≥ log det( Λσn h ) det( Λσ0 h ) = n i=1 log det( Λσi h ) det( Λσi-1 h ) .We can claim that I 2 has at most R h synchronization episodes, otherwiseR h ≥ n i=1 log det( Λσi h ) det( Λσi-1 h ) ≥ i∈{i|σi-1∈I2} log det( Λσi h ) det( Λσi-1 h ) ≥ R h log 3,which causes the contradiction. Thus I 2 has at most R h intervals, then we getk∈I2 m∈M ϕ(z k m,h ) (Λ k m,h ) -1 ≤ R h M √ γ ≤ log det(Λ K h ) det(λI) + 1 M √ γ.Finally, we can bound the total summation,m∈M K k=1 ϕ(z k m,h ) (Λ k m,h ) -1 ≤ m∈M k∈I2 ϕ(z k m,h ) (Λ k m,h ) -1 + m∈M k∈I1∪{K} ∥ϕ(z k m,h )∥ (Λ k m,h ) -1 ≤ log det(Λ K h ) det(λI) + 1 M √ γ + 2 M K log det(Λ K h ) det(λI).This completes the proof.In this section, we prove the regret bound for CoopTS-LMC in the misspecified setting. The regret analysis, the essential supporting lemmas and their corresponding proofs are almost same as what we have presented in Appendix D and Appendix E. Here we mainly point out the differences of proof between these two settings.Definition F.1 (Model prediction error). For any(m, k, h) ∈ M × [K] × [H],we define the model error associated with the reward r m,h ,l k m,h (s, a) = r m,h (s, a) + P m,h V k m,h+1 (s, a) -Q k m,h (s, a). Lemma F.2. Let λ = 1 in Algorithm 3. Under Definition 4.8, for any fixed 0 < δ < 1, with probability at least 1 -δ, for all (m, k, h) ∈ M × [K] × [H] and for any (s, a) ∈ S × A, we have ϕ(s, a) ⊤ w k m,h -r m,h (s, a) -P m,h V k m,h+1 (s, a) ≤ 5H √ dC δ + 3Hζ √ M Kd ∥ϕ(s, a)∥ (Λ k m,h ) -1 + 3Hζ, where C δ is defined in Lemma D.7.Proof of Lemma F.2. Recall from Definition 4.8, we haveP m,h V k m,h+1 (s, a) -ϕ(s, a) ⊤ µ h , V k m,h+1 S ≤ P m,h (• | s, a) -ϕ(s, a), µ h (•) 1 ∥V k m,h+1 ∥ ∞ ≤ 2H P m,h (• | s, a) -ϕ(s, a), µ h (•) TV ≤ 2Hζ,where the first inequality follows from Cauchy-Schwarz inequality, the second inequality follows from the fact that ∥V k m,h+1 ∥ ∞ ≤ H and P 2 , ∥P 1 -P 2 ∥ TV = 1 2 x∈ω |P 1 (x) -P 2 (x)| = 12 ∥P 1 -P 2 ∥ 1 for two distributions P 1 and P 2 , note that here we regard distribution as infinite dimensional vector, the third inequality follows from Definition 4.8. Define ∆m,1 = P m,h V k m,h+1 (s, a) - ϕ(s, a) ⊤ µ h , V k m,h+1 S , thus |∆ m,1 | ≤ 2Hζ. Then we have P m,h V k m,h+1 (s, a) (F.1) = ϕ(s, a) ⊤ µ h , V k m,h+1 S + ∆ m,1 = ϕ(s, a) ⊤ Λ k m,h -1 (s l ,a l ,s ′ l )∈U m,h (k) ϕ s l , a l ϕ s l , a l ⊤ + λI µ h , V k m,h+1 S + ∆ m,1 = ϕ(s, a) ⊤ Λ k m,h -1 (s l ,a l ,s ′ l )∈U m,h (k) ϕ s l , a l ϕ s l , a l ⊤ µ h , V k m,h+1 S + λϕ(s, a) ⊤ Λ k m,h -1 µ h , V k m,h+1 S + ∆ m,1 = ϕ(s, a) ⊤ Λ k m,h -1 (s l ,a l ,s ′ l )∈U m,h (k) ϕ s l , a l P m,h V k m,h+1 s l , a l -ϕ(s, a) ⊤ Λ k m,h -1 (s l ,a l ,s ′ l )∈U m,h (k) ∆ m,1 ϕ s l , a l + λϕ(s, a) ⊤ Λ k m,h -1 µ h , V k m,h+1 S + ∆ m,1 . (F.2)Based on (F.1), we can separate the following error into four parts,EQUATION.We now provide an upper bound for each of the terms in (F.3).Bounding Term (i) in (F.3): same as (E.11) in Appendix E.6, with probability at least 1 -δ, we have|Term (i)| ≤ 3H √ dC δ ∥ϕ(s, a)∥ (Λ k m,h ) -1 . (F.4)Bounding Term (ii) + Term (iv) in (F. EQUATION, (F.5)where the third equality uses the definition of Λ k m,h . By Combining (F.5) and (E.13) in Appendix E.6, we obtain|Term (ii) + Term (iv)| ≤ √ λd∥ϕ(s, a)∥ (Λ k m,h ) -1 + |Term (iv) + Term (v)|. (F.6)Then we calculate that|Term (iv) + Term (v)| = (∆ m,1 + ∆ m,2 )ϕ(s, a) ⊤ Λ k m,h -1 (s l ,a l ,s ′ l )∈U m,h (k) ϕ s l , a l -(∆ m,1 + ∆ m,2 ) ≤ |∆ m,1 + ∆ m,2 | • ϕ(s, a) ⊤ Λ k m,h -1 (s l ,a l ,s ′ l )∈U m,h (k) ϕ s l , a l + |∆ m,1 + ∆ m,2 | ≤ 3Hζ∥ϕ(s, a)∥ (Λ k m,h ) -1 (s l ,a l ,s ′ l )∈U m,h (k) ϕ(s l , a l ) (Λ k m,h ) -1 + 3Hζ ≤ 3Hζ∥ϕ(s, a)∥ (Λ k m,h ) -1 K(k) (s l ,a l ,s ′ l )∈U m,h (k) ϕ(s l , a l ) 2 (Λ k m,h ) -1 1 2 + 3Hζ ≤ 3Hζ √ M Kd∥ϕ(s, a)∥ (Λ k m,h ) -1 + 3Hζ, (F.7)where the second inequality follows from Cauchy-Schwarz inequality and the fact that|∆ m,1 + ∆ m,2 | ≤ |∆ m,1 | + |∆ m,2 | ≤ 2Hζ + ζ ≤ 3Hζ, the third inequality holds because of Cauchy-Schwarz inequality, and the last inequality holds because K(k) ≤ M K and Lemma J.4. Substitute (F.7) into (F.6), we have|Term (ii) + Term (iv)| ≤ 3Hζ √ M Kd + √ λd ∥ϕ(s, a)∥ (Λ k m,h ) -1 + 3Hζ. (F.8)Bounding Term (iii) in (F.3): same as (E.15) in Appendix E.6, we have|Term (iii)| ≤ H √ λd∥ϕ(s, a)∥ (Λ k m,h ) -1 . (F.9)Combine all the terms in (F.3) together: by using triangle inequality in (F.3), we combine (F.4), (F.8) and (F.9), then set λ = 1, with probability at least 1 -δ, we getϕ(s, a) ⊤ w k m,h -r m,h (s, a) -P m,h V k m,h+1 (s, a) ≤ 3H √ dC δ + √ d + H √ d + 3Hζ √ M Kd ∥ϕ(s, a)∥ (Λ k m,h ) -1 + 3Hζ ≤ 5H √ dC δ + 3Hζ √ M Kd ∥ϕ(s, a)∥ (Λ k m,h ) -1 + 3Hζ. This completes the proof. -l k m,h (s, a) ≤ 5H √ dC δ + 3Hζ √ M Kd + 5 2d log √ N /δ 3β K + 4 3 ∥ϕ(s, a)∥ (Λ k m,h ) -1 + 3Hζ,where C δ is defined in Lemma D.7.Proof of Lemma F.3. We do the same process as that in Appendix E.7, and we haveEQUATIONEQUATION.Bounding Term (i): based on (E.16), for any (m, h, k) ∈ M × [H] × [K] and (s, a) ∈ S × A, with probability at least 1 -δ 2 , we havemax n∈[N ] ϕ(s, a) ⊤ w k,J k ,n m,h -ϕ(s, a) ⊤ w k m,h ≤ 5 2d log √ N /δ 3β K + 4 3 ∥ϕ(s, a)∥ (Λ k m,h ) -1 .Bounding Term (ii): based on Lemma F.2, for all (m, h, k)∈ M × [H] × [K] and (s, a) ∈ S × A, we have ϕ(s, a) ⊤ w k m,h -r k h (s, a) -P h V k m,h+1 (s, a) ≤ 5H √ dC δ + 3Hζ √ M Kd ∥ϕ(s, a)∥ (Λ k m,h ) -1 + 3Hζ.Combine the two result above, by taking union bound, with probability at least 1 -δ -δ 2 , we have-l k m,h (s, a) ≤ 5H √ dC δ + 3Hζ √ M Kd + 5 2d log √ N /δ 3β K + 4 3 ∥ϕ(s, a)∥ (Λ k m,h ) -1 + 3Hζ.This completes the proof. l k m,h (s, a) ≤ α δ ε + 3Hζ, where α δ = √ M K 2H √ d + B δ/N M HK .Proof of Lemma F.4. This proof is similar to the proof in Appendix E.8, we just prove the part that for fixed ϕ ∈ C(ε). Recall from Definition F.1,l k m,h (s, a) = r m,h (s, a) + P m,h V k m,h+1 (s, a) -Q k m,h (s, a). Note that Q k m,h (s, a) = min max n∈[N ] ϕ(s, a) ⊤ w k,J k ,n m,h , H -h + 1 + ≤ max n∈[N ] ϕ(x, a) ⊤ w k,J k ,n m,h .Here we defineZ k = r m,h (s, a) + P m,h V k m,h+1 (s, a) -ϕ(s, a) ⊤ µ k,J k m,h -(∆ m,1 + ∆ m,2 ) ϕ(s, a) ⊤ Σ k,J k m,h ϕ(s, a),where ∆ m,1 = P m,h V k m,h+1 (s, a) -ϕ(s, a) ⊤ µ h , V k m,h+1 S , ∆ m,2 = r m,h (s, a) - ϕ(s, a) ⊤ θ h . Based on the results in Proposition D.3, we have that ϕ(s, a) ⊤ w k,J k ,n m,h ∼ N ϕ(s, a) ⊤ µ k,J k m,h , ϕ(s, a) ⊤ Σ k,J k m,h ϕ(s, a) , for any fixed n ∈ [N ]. When |Z k | < 1, by Gaussian concentration Lemma J.10, we haveP r m,h (s, a) + P m,h V k m,h+1 (s, a) -ϕ(s, a) ⊤ w k,J k ,n m,h ≤ (∆m,1 + ∆m,2) = P ϕ(s, a) ⊤ w k,J k ,n m,h ≥ r m,h (s, a) + P m,h V k m,h+1 (s, a) -(∆m,1 + ∆m,2) = P ϕ(s, a) ⊤ w k,J k ,n m,h -ϕ(s, a) ⊤ µ k,J k m,h ϕ(s, a) ⊤ Σ k,J k m,h ϕ(s, a) ≥ r m,h (s, a) + P m,h V k m,h+1 (s, a) -(∆m,1 + ∆m,2) -ϕ(s, a) ⊤ µ k,J k m,h ϕ(s, a) ⊤ Σ k,J k m,h ϕ(s, a) = P ϕ(s, a) ⊤ w k,J k ,n m,h -ϕ(s, a) ⊤ µ k,J k m,h ϕ(s, a) ⊤ Σ k,J k m,h ϕ(s, a) ≥ Z k ≥ 1 2 √ 2π exp(-Z 2 k /2) ≥ 1 2 √ 2eπ .Consider the numerator of Z k :r m,h (s, a) + P m,h V k m,h+1 (s, a) -ϕ(s, a) ⊤ µ k,J k m,h -(∆ m,1 + ∆ m,2 ) ≤ r m,h (s, a) + P m,h V k m,h+1 (s, a) -ϕ(s, a) ⊤ w k m,h -(∆ m,1 + ∆ m,2 ) I1 + ϕ(s, a) ⊤ w k m,h -ϕ(s, a) ⊤ µ k,J k m,h I2 . (F.10)Bounding Term I 1 in (F.10): recall the proof of Lemma F.2, we do the almost same error decomposition as (F.3) with the only difference of adding termEQUATION.(F.11)We now provide an upper bound for each of the terms in (F.11).Bounding Term (i) in (F.11): almost same as (E.11) in Appendix E.6 with the only difference between P h and P m,h , with probability at least 1 -δ, we have|Term (i)| ≤ 3H √ dC δ ∥ϕ(s, a)∥ (Λ k m,h ) -1 . (F.12)Bounding Term (ii) + Term (iv) in (F.11): we do the same calculation as that in the proof of Lemma F.2, based on (F.5), we haveEQUATION.(F.13)By Combining (F.13) and (E.13) in Appendix E.6, we obtain|Term (ii) + Term (iv)| ≤ √ λd∥ϕ(s, a)∥ (Λ k m,h ) -1 + |Term (iv) + Term (v)|. (F.14)Then we calculate that|Term (iv) + Term (v)| = |∆ m,1 + ∆ m,2 | • ϕ(s, a) ⊤ Λ k m,h -1 (s l ,a l ,s ′ l )∈U m,h (k) ϕ s l , a l ≤ 3Hζ∥ϕ(s, a)∥ (Λ k m,h ) -1 (s l ,a l ,s ′ l )∈U m,h (k) ϕ(s l , a l ) (Λ k m,h ) -1 ≤ 3Hζ∥ϕ(s, a)∥ (Λ k m,h ) -1 K(k) (s l ,a l ,s ′ l )∈U m,h (k) ϕ(s l , a l ) 2 (Λ k m,h ) -1 1 2 ≤ 3Hζ √ M Kd∥ϕ(s, a)∥ (Λ k m,h ) -1 , (F.15)where the first inequality follows from Cauchy-Schwarz inequality and the fact that |∆ m,1 + ∆ m,2 | ≤ 3Hζ, the second inequality holds because of Cauchy-Schwarz inequality, and the last inequality holds because K(k) ≤ M K and Lemma J.4. Substitute (F.15) into (F.14), we have|Term (ii) + Term (iv)| ≤ 3Hζ √ M Kd + √ λd ∥ϕ(s, a)∥ (Λ k m,h ) -1 . (F.16)Bounding Term (iii) in (F.11): same as (E.15) in Appendix E.6, we have|Term (iii)| ≤ H √ λd∥ϕ(s, a)∥ (Λ k m,h ) -1 . (F.17)Combine all the terms in (F.11) together: by using triangle inequality in (F.11), we combine (F.12), (F. 16 ) and (F.17), then set λ = 1, with probability at least 1 -δ, we getϕ(s, a) ⊤ w k m,h -r m,h (s, a) -P m,h V k m,h+1 (s, a) + (∆ m,1 + ∆ m,2 ) ≤ 5H √ dC δ + 3Hζ √ M Kd ∥ϕ(s, a)∥ (Λ k m,h ) -1 .Bounding Term I 2 in (F.10): same as the proof in Appendix E.8, we haveϕ(s, a) ⊤ w k m,h -ϕ(s, a) ⊤ µ k,J k m,h ≤ 4 3 ∥ϕ(s, a)∥ (Λ k m,h ) -1 .So, with probability at least 1 -δ, we haver m,h (s, a) + P m,h V k m,h+1 (s, a) -ϕ(s, a) ⊤ µ k,J k m,h ≤ 5H √ dC δ + 3Hζ √ M Kd + 4 3 ∥ϕ(s, a)∥ (Λ k m,h ) -1 . (F.18)Consider the denominator of Z k : same as the proof in Appendix E.8, with (E.18), we have∥ϕ(s, a)∥ Σ k,J k m,h ≥ 1 4 √ β K ∥ϕ(s, a)∥ (Λ k m,h ) -1 , (F.19)where we used the fact that λ min Λ k m,h-1 ≥ 1/k and ∥ϕ(s, a)∥ (Λ k m,h ) -1 ≥ 1/ √ k∥ϕ(s, a)∥ 2 .Therefore, according to (F.18) and (F. 19) , with probability at least 1 -δ, it holds that|Z k | = r m,h (s, a) + P m,h V k m,h+1 (s, a) -ϕ(s, a) ⊤ µ k,J k m,h ϕ(s, a) ⊤ Σ k,J k m,h ϕ(s, a) ≤ 5H √ dC δ + 3Hζ √ M Kd + 4 3 ∥ϕ(s, a)∥ (Λ k m,h ) -1 1 4 √ β K ∥ϕ(s, a)∥ (Λ k m,h ) -1 = 5H √ dC δ + 3Hζ √ M Kd + 4 3 1 4 √ β K , which implies |Z k | < 1 when 1 √ β K = 20H √ dC δ + 12Hζ √ M Kd + 163 . Now we have already proved that, for any fixed n ∈ [N ], with probability at least 1 -δ, we haveP r m,h (s, a) + P m,h V k m,h+1 (s, a) -ϕ(s, a) ⊤ w k,J k ,n m,h ≤ (∆ m,1 + ∆ m,2 ) ≥ 1 2 √ 2eπ .By taking union bound over n ∈ [N ], with probablity at least 1 -δ, we haveP max n∈[N ] ϕ(s, a) ⊤ w k,J k ,n m,h -r m,h (s, a) -P m,h V k m,h+1 (s, a) ≥ -(∆ m,1 + ∆ m,2 ) ≥ 1 -1 - 1 2 √ 2eπ N = 1 -c ′ 0 N , where c ′ 0 = 1 -1 2 √ 2eπ . Finally, with probability at least (1 -δ) 1 -c ′ 0 N , for all (s, a) ∈ S × A,we have l k m,h (s, a) ≤ 3Hζ. Till now we have completed the proof of fixed ϕ ∈ C(ε). Follow the proof in Appendix E.8, we can get the final result.In this part, we give out the proof of Theorem 4.12, the regret bound for CoopTS-LMC in the misspecified setting.Proof of Theorem 4.12. This proof is almost same as the proof in Appendix D.2. We do the same regret decomposition (D.2) and obtain the same bound for Term(i) (D.3) and Term(ii) (D.4). Next we bound Term (iii) with new lemmas in the misspecified setting.Bounding Term (iii) in (D.2): based on Lemma F.3 and Lemma F.4, by taking union bound, with probability at least1 -|C(ε)|c ′ 0 N -2δ ′ -M HK(δ ′ + δ ′ 2 ), we have m∈M K k=1 H h=1 E π * l k m,h (s m,h , a m,h )|s m,1 = s k m,1 -l k m,h s k m,h , a k m,h ≤ m∈M K k=1 H h=1 -l k m,h s k m,h , a k m,h + α δ ′ ε + 3Hζ ≤ m∈M K k=1 H h=1 5H √ dC δ ′ + 3Hζ √ M Kd + 5 2d log √ N /δ ′ 3β K + 4 3 ϕ(s k m,h , a k m,h ) (Λ k m,h ) -1 + α δ ′ ε + 6Hζ = HM Kα δ ′ ε + 6H 2 M Kζ + 5H √ dC δ ′ + 3Hζ √ M Kd + 5 2d log √ N /δ ′ 3β K + 4 3 × H h=1 m∈M K k=1 ϕ(s k m,h , a k m,h ) (Λ k m,h ) -1 ≤ HM Kα δ ′ ε + 6H 2 M Kζ + 5H √ dC δ ′ + 3Hζ √ M Kd + 5 2d log √ N /δ ′ 3β K + 4 3 × H h=1 log det(Λ K h ) det(λI) + 1 M √ γ + 2 M K log det(Λ K h ) det(λI) ≤ HM Kα δ ′ ε + 6H 2 M Kζ + 5H √ dC δ ′ + 3Hζ √ M Kd + 5 2d log √ N /δ ′ 3β K + 4 3 × H d(log(1 + M K/d) + 1)M √ γ + 2 M Kd log(1 + M K/d) = O d 3 2 H 2 √ M dM γ + √ K + d 3 2 H 2 M √ K dM γ + √ K ζ . (F.20)The first inequality follows from Lemma F.4, the second inequality follows from Lemma F.3, the third inequality follows from Lemma D.12, the last inequality holds due to Lemma J.2 and the fact that ∥ϕ(•)∥ 2 ≤ 1, the last equality follows from 1 16 3 , which we define in Lemma F.4.√ β K = 20H √ dC δ ′ + 12Hζ √ M Kd +The probability calculation is same as that in Appendix D.2. By combining Terms (i)(ii)(iii) together, we get that the final regret bound for CoopTS-LMC in misspecified setting isO d 3 2 H 2 √ M dM γ + √ K + d 3 2 H 2 M √ K dM γ + √ K ζ ,with probability at least 1 -δ. Here we finish the proof.Before getting the regret bound for CoopTS-PHE, we first present some essential technical lemmas required for our analysis.Proposition G.1. The difference between the perturbed estimated parameter w k,n m,h and unperturbed estimated parameter w k m,h satisfies the Gaussian distribution,ζ k,n m,h = w k,n m,h -w k m,h ∼ N 0, σ 2 Λ k m,h -1 , where w k m,h = Λ k m,h -1 (s l ,a l ,s ′ l )∈U m,h (k) r h + V k m,h+1 s ′ l ϕ s l , a l is the unperturbed estimated parameter.Next we will define some good events that hold with high probability to help prove the critical lemmas in this section.Lemma G.2 (Good events). For any fixed 0 < δ < 1, with some constant c > 0, we define the following random eventsG k m,h (ζ, δ) def = max n∈[N ] ζ k,n m,h Λ k m,h ≤ c 1 σ √ d , G(M, K, H, δ) def = m∈M k≤K h≤H G k m,h (ζ, δ),where c 1 = c log(dN M KH/δ). Then the event G(M, K, H, δ) occurs with probability at least 1 -δ.Lemma G.3. Let λ = 1 in Algorithm 2. For any fixed 0 < δ < 1, conditioned on the event G(M, K, H, δ), with probability1 -δ, for all (m, k, h) ∈ M × [K] × [H], we have (s l ,a l ,s ′ l )∈U m,h (k) ϕ s l , a l V k m,h+1 -P h V k m,h+1 s l , a l (Λ k m,h ) -1 ≤ 3H √ dD δ ,where we defineD δ = 1 2 log(K + 1) + log 6 √ 2K(2H √ M Kd+c1σ √ d) H + log 1 δ 1/2 . Lemma G.4. Let λ = 1 in Algorithm 2. Under Definition 4.1, for any fixed 0 < δ < 1, conditioned on the event G(M, K, H, δ), with probability 1 -δ, for all (m, k, h) ∈ M × [K] × [H] and for any (s, a) ∈ S × A, we have ϕ(s, a) ⊤ w k m,h -r h (s, a) -P h V k m,h+1 (s, a) ≤ 5H √ dD δ ∥ϕ(s, a)∥ (Λ k m,h ) -1 . (G.1)Lemma G.5 (Optimism). Let λ = 1 in Algorithm 2 and set c 0 = Φ(1). Under Definition 4.1, conditioned on the event G(M, K, H, δ), with probability at least1 -|C(ε)|c N 0 -δ where |C(ε)| ≤ (3/ε) d , for all (m, k, h) ∈ M × [K] × [H]and for all (s, a) ∈ S × A, we havel k m,h (s, a) ≤ A δ ε, where A δ = c 1 σ √ d + 5H √ dD δ = O(Hd).Lemma G.6 (Error bound). Let λ = 1 in Algorithm 2. Under Definition 4.1, for any fixed 0 < δ < 1, conditioned on the event G(M, K, H, δ), with probability 1 -δ, for all (m, k, h)∈ M × [K] × [H]and for any (s, a) ∈ S × A, we have-l k m,h (s, a) ≤ c 2 Hd∥ϕ(s, a)∥ (Λ k m,h ) -1 ,where c 2 = O(1).In this part, we give out the proof of Theorem 4.2, the regret bound for CoopTS-PHE.Proof of Theorem 4.2. Based on the result from Lemma D.13, we do the regret decomposition firstEQUATIONEQUATIONEQUATION.(G.2)Next, we will bound the above three terms respectively.Bounding Term (i) in (G.2): for the policy π k m,h , we havem∈M K k=1 H h=1 E π * Q k m,h (s m,h , •), π * m,h (•, |s m,h ) -π k m,h (•|s m,h ) |s m,1 = s k m,1 ≤ 0. (G.3)This is because by definition π k m,h is the greedy policy forQ k m,h . Bounding Term (ii) in (G.2): note that 0 ≤ Q k m,h ≤ H -h + 1 ≤ H, based on (D.1), for any (m, k, h) ∈ M × [K] × [H], we have |D m,k,h,1 | ≤ 2H and |D m,k,h,2 | ≤ 2H. Note that D m,k,h,1 is a martingale difference sequence E[D m,k,h,1 |F m,k,h ] = 0.By applying Azuma-Hoeffding inequality, with probability at least 1 -δ/3, we havem∈M K k=1 H h=1 D m,k,h,1 ≤ 2 2M H 3 K log(6/δ).Note that D m,k,h,2 is also a martingale difference sequence. By applying Azuma-Hoeffding inequality, with probability at least 1 -δ/3, we havem∈M K k=1 H h=1 D m,k,h,2 ≤ 2 2M H 3 K log(6/δ).By taking union bound, with probability at least 1 -2δ/3, we havem∈M K k=1 H h=1 D m,k,h,1 + m∈M K k=1 H h=1 D m,k,h,2 ≤ 4 2M H 3 K log(6/δ).(G.4)Bounding Term (iii) in (G.2): conditioned on the event G(M, K, H, δ ′ ), based on Lemma G.6 and Lemma G.5, by taking union bound, with probability at least1 -|C(ε)|c N 0 -δ ′ -M HKδ ′ , we have m∈M K k=1 H h=1 E π * l k m,h (s m,h , a m,h )|s m,1 = s k m,1 -l k m,h s k m,h , a k m,h ≤ m∈M K k=1 H h=1 A δ ′ ε -l k m,h s k m,h , a k m,h ≤ HM KA δ ′ ε + m∈M K k=1 H h=1 c 2 dH ϕ(s k m,h , a k m,h ) (Λ k m,h ) -1 ≤ HM KA δ ′ ε + c 2 dH H h=1 log det(Λ K h ) det(λI) + 1 M √ γ + 2 M K log det(Λ K h ) det(λI) ≤ HM KA δ ′ ε + c 2 dH • H d(log(1 + M K/d) + 1)M √ γ + 2 M Kd log(1 + M K/d) .The first inequality follows from Lemma G.5, the second inequality holds due to Lemma G.6, the third inequality follows from Lemma D.12, the last inequality holds due to Lemma J.2 and the fact that ∥ϕ(•)∥ 2 ≤ 1.ε = dH d/M K/A δ ′ = O( d/M K). Conditioned on the event G(M, K, H, δ ′ ), we have m∈M K k=1 H h=1 Eπ * l k m,h (s m,h , a m,h )|sm,1 = s k m,1 -l k m,h s k m,h , a k m,h ≤ O dH 2 dM √ γ + √ dM K , (G.5)with probability at least 1-|C(ε)|c N 0 -δ ′ -M HKδ ′ . Based on Lemma G.2, the event G(M, K, H, δ ′ ) occurs with probability at least 1 -δ ′ . Therefore, (G.5) occurs with probability at least1 -δ ′ 1 -|C(ε)|c N 0 -δ ′ -M HKδ ′ .We set δ ′ = δ/6(M HK + 2) and choose N = C log(δ)/ log(c 0 ) where C = O(d), then we have Proof. Based on (3.5), we can calculate that1 -δ ′ 1 -|C(ε)|c N 0 -δ ′ -M HKδ ′ ≥ 1 -δ/3. Combining Terms (i)(ii)(iiiEQUATIONwherew k m,h = Λ k m,h -1 (s l ,a l ,s ′ l )∈U m,h (k) r h + V k m,h+1 s ′ l ϕ s l , a l is the unperturbed estimated parameter. Since ϵ k,l,n h ∼ N (0, σ 2 ), for l ∈ [K(k)],based on the property of Gaussian distribution, we have ϵ k,l,n h ϕ s l , a l ∼ N 0, σ 2 ϕ s l , a l ϕ s l , a l ⊤ , Since ξ k,n h ∼ N (0, σ 2 I), we can calculate the covariance matrix of the second term in (H.1),Λ k m,h -1 Cov (s l ,a l ,s ′l )∈U m,h (k) ϵ k,l,n h ϕ s l , a l -λξ k,n h Λ k m,h -1 = Λ k m,h -1 σ 2 (s l ,a l ,s ′ l )∈U m,h (k) ϕ s l , a l ϕ s l , a l ⊤ + λI Λ k m,h -1 = σ 2 Λ k m,h -1 Λ k m,h Λ k m,h -1 = σ 2 Λ k m,h -1 .It is obvious that the mean of the second term in (H.1) is 0. Thus, we haveζ k,n m,h = w k,n m,h -w k m,h ∼ N 0, σ 2 Λ k m,h -1 .This completes the proof.Proof. Recall that in Proposition G.1, we haveEQUATIONBy Lemma J.10, for fixed n ∈ [N ], with probability at least 1 -δ, we haveζ k,n m,h Λ k m,h ≤ c dσ 2 log(d/δ).By applying union bound over N samples, we haveP max n∈[N ] ζ k,n m,h Λ k m,h ≤ c dσ 2 log(d/δ) ≥ 1 -N δ.Now we define c 1 = c log(dN M KH/δ), and we define the eventG k m,h (ζ, δ) def = max n∈[N ] ζ k,n m,h Λ k m,h ≤ c 1 σ √ d .Thus for any fixed m, h and k, the event G k m,h (ζ, δ) occurs with a probability of at least 1 -δ/M KH. By taking union bound over all (m, h, k)∈ M × [H] × [K], we have P G(M, K, H, δ) = P m∈M k≤K h≤H G k m,h (ζ, δ) ≥ 1 -δ.This completes the proof.Proof. Based on the result in Lemma D.4, for any(m, h, k) ∈ M × [H] × [K],we havew k m,h ≤ 2H M kd/λ.By recalling the construction of Λ k m,h , it is trivial to find that λ min Λ k m,h ≥ λ. Conditioned on the event G(M, K, H, δ), we have√ λ ζ k,n m,h ≤ ζ k,n m,h Λ k m,h ≤ c 1 σ √ d.Then by triangle inequality, for all n ∈ [N ], we obtain the upper boundw k,n m,h = w k m,h + ζ k,n m,h ≤ 2H M kd/λ + c 1 σ d/λ.Based on the result from Lemma J.7 and Lemma J.9, we have that, for any ε > 0, and for all (m, k, h) ∈ M × [K] × [H], with probability at least 1 -δ, we have(s l ,a l ,s ′ l )∈U m,h (k) ϕ s l , a l V k m,h+1 -P h V k m,h+1 s l , a l (Λ k m,h ) -1 ≤ 4H 2 d 2 log k + λ λ + d log 3 2H M kd/λ + c 1 σ d/λ ε + log 1 δ + 8k 2 ε 2 λ 1/2 ≤ 2H d 2 log k + λ λ + d log 3 2H M kd/λ + c 1 σ d/λ ε + log 1 δ 1/2 + 2 √ 2kε √ λ .Here we set λ = 1, ε = H 2 √ 2k , with probability at least 1 -δ, we have(s l ,a l ,s ′ l )∈U m,h (k) ϕ s l , a l V k m,h+1 -P h V k m,h+1 s l , a l (Λ k m,h ) -1 ≤ 2H √ d 1 2 log(K + 1) + log 6 √ 2K 2H √ M Kd + c 1 σ √ d H + log 1 δ 1/2 + H ≤ 3H √ dD δ ,where we define D δ = 1 2 log(K + 1) + log 6√ 2K(2H √ M Kd+c1σ √ d) H + log 1 δ 1/2. Here we finish the proof.Proof. This proof is almost same as the proof of Lemma D.8 in Appendix E.6. The only difference is the Term (i) in (E.10). Here based on Lemma G.6, conditioned on the event G(M, K, H, δ), with probability 1 -δ, we haveTerm (i) ≤ 3H √ dD δ ∥ϕ(s, a)∥ (Λ k m,h ) -1 .Finally, conditioned on the event G(M, K, H, δ), with probability 1 -δ, for all (m, k, h) ∈ M × [K] × [H] and for any (s, a) ∈ S × A, we haveϕ(s, a) ⊤ w k m,h -r h (s, a) -P h V k m,h+1 (s, a) ≤ 3H √ dD δ + H √ d + √ d ∥ϕ(s, a)∥ (Λ k m,h ) -1 ≤ 5H √ dD δ ∥ϕ(s, a)∥ (Λ k m,k ) -1 .Here we finish the proof.Proof. Recall from Definition 4.1, we haver h (s, a) + P h V k m,h+1 (s, a) = ϕ(s, a) ⊤ θ h + ϕ(s, a) ⊤ µ h , V k m,h+1 S def = ϕ(s, a) ⊤ w k m,h , where w k m,h = θ h + µ h , V k m,h+1 S . Note that max{∥µ h (S)∥, ∥θ h ∥} ≤ √ d and V k m,h+1 ≤ H -h ≤ H, thus we have w k m,h ≤ ∥θ h ∥ + µ h , V k m,h+1 S ≤ √ d + H √ d ≤ 2H √ d.Then we define the regression error ∆w k m,h = w k m,h -w k m,h . For any (m, h, k) ∈ M × [H] × [K] and any (s, a) ∈ S × A, we havel k m,h (s, a) = r h (s, a) + P h V k m,h+1 (s, a) -Q k m,h (s, a) = r h (s, a) + P h V k m,h+1 (s, a) -min H -h + 1, max n∈[N ] ϕ(s, a) ⊤ w k m,h + ζ k,n m,h + ≤ max ϕ(s, a) ⊤ w k m,h -(H -h + 1), ϕ(s, a) ⊤ w k m,h -max n∈[N ] ϕ(s, a) ⊤ w k m,h + ζ k,n m,h ≤ max 0, ϕ(s, a) ⊤ ∆w k m,h -max n∈[N ] ϕ(s, a) ⊤ ζ k,n m,h , (H.2)where the last inequality holds because|r h | ≤ 1 and V k m,h+1 ≤ H -h, this indicates r h (s, a) + P h V k m,h+1 (s, a) = ϕ(s, a) ⊤ w k m,h ≤ H -h + 1. Note that ∥ϕ(s, a)∥ (Λ k m,h ) -1 ≤ 1/λ∥ϕ(s, a)∥ ≤ 1 for all ϕ(s, a). Define C(ε) to be a ε-cover of ϕ | ∥ϕ∥ (Λ k m,h ) -1 ≤ 1 . Based on Lemma J.8, we have |C(ε)| ≤ (3/ε) d .First, for any fixed ϕ(s, a) ∈ C(ε), we haveϕ ⊤ ζ k,n m,h ∼ N 0, σ 2 ∥ϕ∥ 2 (Λ k m,h ) -1 .Use the property of Gaussian distribution, we obtainP ϕ ⊤ ζ k,n m,h -σ∥ϕ∥ (Λ k m,h ) -1 ≥ 0 = Φ(-1). By taking union bound over n ∈ [N ], we obtainP max n∈[N ] ϕ ⊤ ζ k,n m,h -σ∥ϕ∥ (Λ k m,h ) -1 ≥ 0 ≥ 1 -(1 -Φ(-1)) N = 1 -Φ(1) N = 1 -c N 0 .By applying union bound over C(ε), with probability 1 -|C(ε)|c N 0 , for all ϕ ∈ C(ε), we havemax n∈[N ] ϕ ⊤ ζ k,n m,h -σ∥ϕ∥ (Λ k m,h ) -1 ≥ 0. (H.3)Then, for any ϕ = ϕ(s, a), we can findϕ ′ ∈ C(ε) such that ∥ϕ -ϕ ′ ∥ (Λ k m,h ) -1 ≤ ε. Define ∆ϕ = ϕ -ϕ ′ , we have ϕ ⊤ ζ k,n m,h -ϕ ⊤ ∆w k m,h = ϕ ′ ⊤ ζ k,n m,h -ϕ ′ ⊤ ∆w k m,h + ∆ϕ ⊤ ζ k,n m,h -∆ϕ ⊤ ∆w k m,h ≥ ϕ ′ ⊤ ζ k,n m,h -∥ϕ ′ ∥ (Λ k m,h ) -1 ∆w k m,h Λ k m,h -∥∆ϕ∥ (Λ k m,h ) -1 ζ k,n m,h Λ k m,h -∥∆ϕ∥ (Λ k m,h ) -1 ∆w k m,h Λ k m,h ≥ ϕ ′ ⊤ ζ k,n m,h -∥ϕ ′ ∥ (Λ k m,h ) -1 ∆w k m,h Λ k m,h -ε ζ k,n m,h Λ k m,h + ∆w k m,h Λ k m,h . (H.4)Conditioned on the event G(M, K, H, δ), we haveζ k,n m,h Λ k m,h ≤ c 1 σ √ d.For any vector x ∈ R d , we havex ⊤ ∆w k m,h = x ⊤ w k m,h -w k m,h = x ⊤ Λ k m,h -1 Λ k m,h w k m,h - (s l ,a l ,s ′ l )∈U m,h (k) r h + V k m,h+1 s ′ l ϕ s l , a l = x ⊤ Λ k m,h -1 K(k) l=1 ϕ s l , a l ϕ s l , a l ⊤ w k m,h + λw k m,h - K(k) l=1 r h + V k m,h+1 s ′ l ϕ s l , a l = x ⊤ Λ k m,h -1 w k m,h + K(k) l=1 P h V k m,h+1 -V k m,h+1 s ′ l ϕ s l , a l ,where the third equality holds due to the definition of Λ k m,h . We set x = Λ k m,h ∆w k m,h . By using Cauchy-Schwarz inequality, we have∆w k m,h 2 Λ k m,h = ∆w k m,h ⊤ w k m,h + K(k) l=1 P h V k m,h+1 -V k m,h+1 s ′ l ϕ s l , a l ≤ ∆w k m,h Λ k m,h • w k m,h + K(k) l=1 P h V k m,h+1 -V k m,h+1 s ′ l ϕ s l , a l (Λ k m,h ) -1.This indicates that with probability at least 1 -δ, for all (m, h, k)∈ M × [H] × [K], we have ∆w k m,h Λ k m,h ≤ w k m,h (Λ k m,h ) -1 + K(k) l=1 P h V k m,h+1 -V k m,h+1 s ′ l ϕ s l , a l (Λ k m,h ) -1 ≤ w k m,h + 3H √ dD δ ≤ 5H √ dD δ ,where the second inequality holds because of Lemma G.3. Then for all (m, h, k)∈ M × [H] × [K],with probability at least 1 -δ, (H.4) becomesmax n∈[N ] ϕ ⊤ ζ k,n m,h -ϕ ⊤ ∆w k m,h ≥ max n∈[N ] ϕ ′ ⊤ ζ k,n m,h -∥ϕ ′ ∥ (Λ k m,h ) -1 ∆w k m,h Λ k m,h -ε c 1 σ √ d + 5H √ dD δ . Now we choose σ = O(H √ d) and guarantee that σ > 5H √ dD δ ≥ ∆w k m,h Λ k m,h , this is achievable through calculation. Define A δ = c 1 σ √ d + 5H √ dD δ = O(Hd). Then, for all (m, h, k) ∈ M × [H] × [K], with probability at least 1 -δ, we havemax n∈[N ] ϕ ⊤ ζ k,n m,h -ϕ ⊤ ∆w k m,h ≥ max n∈[N ] ϕ ′ ⊤ ζ k,n m,h -σ∥ϕ ′ ∥ (Λ k m,h ) -1 -A δ ε.Recall from (H.3), by taking union bound, with probability at least 1 -|C(ε)|c N 0 -δ, for all (m, h, k) ∈ M × [H] × [K] and for all (s, a) ∈ S × A, we have max n∈[N ] ϕ ⊤ ζ k,n m,h -ϕ ⊤ ∆w k m,h ≥ -A δ ε.EQUATION-l k m,h (s, a) ≤ 5H √ dD δ + c 1 σ √ d ∥ϕ(s, a)∥ (Λ k m,h ) -1 ≤ c 2 Hd∥ϕ(s, a)∥ (Λ k m,h ) -1, where c 2 = O(1). Here we completes the proof.In this section, we prove the regret bound for CoopTS-PHE in the misspecified setting. The regret analysis, the essential supporting lemmas and their corresponding proofs are very similar to what we have presented in Appendix G and Appendix H. Here we mainly point out the differences of proof between these two settings.Lemma I.1. Let λ = 1 in Algorithm 2. Under Definition 4.8, for any fixed 0 < δ < 1, conditioned on the event G(M, K, H, δ), with probability 1 -δ, for all (m, k, h) ∈ M × [K] × [H] and for any (s, a) ∈ S × A, we haveϕ(s, a) ⊤ w k m,h -r h (s, a) -P h V k m,h+1 (s, a) ≤ 5H √ dD δ + 3Hζ √ M Kd ∥ϕ(s, a)∥ (Λ k m,h ) -1 + 3Hζ, (I.1)where D δ is defined in Lemma G.3.Proof of Lemma I.1. This proof is almost same as the proof of Lemma F.2, with the only difference in bounding Term(i) in (F.3). Here (F.4) becomes|Term(i)| ≤ 3H √ dD δ ∥ϕ(s, a)∥ (Λ k m,h ) -1 .Finally we can get the desired result. l k m,h ≤ A δ ε + 3Hζ, where A δ = c 1 σ √ d + 5H √ dD δ = O(Hd).Proof of Lemma I.2. This proof is similar to the proof in Appendix H.5. In the previous part, we have defined ∆ m,1 = P m,h V k m,h+1 (s, a) -ϕ(s, a) ⊤ µ h , V k m,h+1 S , ∆ m,2 = r m,h (s,l k m,h (s, a) = r m,h (s, a) + P m,h V k m,h+1 (s, a) -Q k m,h (s, a) = r m,h (s, a) + P m,h V k m,h+1 (s, a) -min H -h + 1, max n∈[N ] ϕ(s, a) ⊤ w k m,h + ζ k,n m,h + ≤ max ϕ(s, a) ⊤ w k m,h -(H -h + 1), ϕ(s, a) ⊤ w k m,h -max n∈[N ] ϕ(s, a) ⊤ w k m,h + ζ k,n m,h + ∆ m,1 + ∆ m,2 ≤ max 0, ϕ(s, a) ⊤ ∆w k m,h -max n∈[N ] ϕ(s, a) ⊤ ζ k,n m,h + 3Hζ. (I.2)In Appendix H.5, we have proved that with probability at least1 -|C(ε)|c N 0 -δ, for all (m, h, k) ∈ M × [H] × [K]and for all (s, a) ∈ S × A, we havemax n∈[N ] ϕ ⊤ ζ k,n m,h -ϕ ⊤ ∆w k m,h ≥ -A δ ε.Substitute it into (I.2), we can get the final result. Proof of Lemma I.3. Similar to the proof in Appendix H.6, using (H.6) in Appendix H.6 and (I.1), we have-l k m,h (s, a) ≤ r h (s, a) + P h V k m,h+1 (s, a) -ϕ(s, a) ⊤ w k m,h + max n∈[N ] ϕ(s, a) ⊤ ζ k,n m,h ≤ 5H √ dD δ + 3Hζ √ M Kd + c 1 σ √ d ∥ϕ(s, a)∥ (Λ k h ) -1 + 3Hζ ≤ c 2 Hd + 3Hζ √ M Kd ∥ϕ(s, a)∥ (Λ k h ) -1 + 3Hζ,where c 2 = O(1) is same as that in Lemma G.6. Here we completes the proof.In this part, we give out the proof of Theorem 4. E π * l k m,h (s m,h , a m,h )|s m,1 = s k m,1 -l k m,h s k m,h , a k m,h ≤ m∈M K k=1 H h=1 -l k m,h s k m,h , a k m,h + A δ ′ ε + 3Hζ ≤ m∈M K k=1 H h=1 c 2 dH + 3Hζ √ M Kd ∥ϕ(s, a)∥ (Λ k h ) -1 + 3Hζ + A δ ′ ε + 3Hζ = HM KA δ ′ ε + 6H 2 M Kζ + c 2 dH + 3Hζ √ M Kd H h=1 m∈M K k=1 ϕ(s k m,h , a k m,h ) (Λ k m,h ) -1 ≤ HM KA δ ′ ε + 6H 2 M Kζ + c 2 dH + 3Hζ √ M Kd × H h=1 log det(Λ K h ) det(λI) + 1 M √ γ + 2 M K log det(Λ K h ) det(λI) ≤ HM KA δ ′ ε + 6H 2 M Kζ + c 2 dH + 3Hζ √ M Kd × H d(log(1 + M K/d) + 1)M √ γ + 2 M Kd log(1 + M K/d) = O d 3 2 H 2 √ M dM γ + √ K + dH 2 M √ K dM γ + √ K ζ .The first inequality follows from Lemma I.2, the second inequality holds due to Lemma I.3, the third inequality follows from Lemma D.12, the last inequality holds due to Lemma J.2 and the fact that ∥ϕ(•)∥ 2 ≤ 1, and again we chooseε = dH d/M K/A δ ′ = O( d/M K).The probability calculation is same as that in Appendix G.2. By combining Terms (i)(ii)(iii) together, we get that the final regret bound for CoopTS-PHE in misspecified setting isRegret(K) = O d 3 2 H 2 √ M dM γ + √ K + dH 2 M √ K dM γ + √ K ζ ,with probability at least 1 -δ. Here we finish the proof.Lemma J.9. Let V denote a class of functions mapping from S to R with the following parametric formV (•) = max a∈A min max n∈[N ] ϕ(•, a) ⊤ w n , H -h + 1 + ,where the parameter w n satisifies ∥w n ∥ ≤ B for all n ∈ [N ] and for all (x, a) ∈ S × A, we have ∥ϕ(x, a)∥ ≤ 1. Let N V,ε be the ε-covering number of V with respect to the distance dist(V, V ′ ) = sup s∈S V (s) -V ′ (s) . Then N V,ε ≤ 3B ε d . Proof. Consider any two functions V 1 , V 2 ∈ V with parameters {w n 1 } n∈[N ] and {w n 2 } n∈[N ] respec- tively. Then we have dist(V 1 , V 2 ) ≤ sup s,a max n∈[N ] ϕ(s, a) ⊤ w n 1 -max n∈[N ] ϕ(s, a) ⊤ w n 2 ≤ sup s,a max n∈[N ] ϕ(s, a) ⊤ w n 1 -ϕ(s, a) ⊤ w n 2 ≤ sup ∥ϕ∥≤1 max n∈[N ] ϕ ⊤ w n 1 -ϕ ⊤ w n 2 = max n∈[N ] sup ∥ϕ∥≤1 ϕ ⊤ (w n 1 -w n 2 ) ≤ max n∈[N ] sup ∥ϕ∥≤1 ∥ϕ∥ w n 1 -w n 2 ≤ max n∈[N ] w n 1 -w n 2 .Let N w,ε denote the ε-covering number of {w ∈ R d | ∥w∥ ≤ B}. Then, Lemma J.8 impliesN w,ε ≤ 1 + 2B ε d ≤ 3B ε d . For any V 1 ∈ V, we consider its corresponding parameters {w n 1 } n∈[N ] . For any n ∈ [N ], we can find w n 2 such that ∥w n 1 -w n 2 ∥ ≤ ε, then we can get V 2 ∈ V with parameters {w n 2 } n∈[N ] . Then we have dist(V 1 , V 2 ) ≤ max n∈[N ] ∥w n 1 -w n 2 ∥ ≤ ε. Thus, we have, N V,ε ≤ N w,ε ≤ 1 + 2B ε d ≤ 3B ε d .This completes the proof.Lemma J.10. [3] Suppose Z is a Gaussian random variable Z ∼ N (µ, σ 2 ), where σ > 0. For 0 ≤ z ≤ 1, we haveEQUATION2 .And for z ≥ 1, we havee -z 2 /2 2z √ π ≤ P(|Z -µ| > zσ) ≤ e -z 2 /2 z √ π .Lemma J.11. [32, Lemma D.2] Consider a d-dimensional multivariate normal distribution N 0, AΛ -1 where A is a scalar. Let η 1 , η 2 , . . . , η N be N independent samples from the distribution. Then for any δ > 0P max j∈[M ] ∥η j ∥ Λ ≤ c dA log(d/δ) ≥ 1 -M δ,where c is some absolute constant. Lemma J.12. [1, Lemma 12] Let A, B and C be positive semi-definite matrices such that A = B + C. Then we have that sup x̸ =0 x ⊤ Ax x ⊤ Bx ≤ det(A) det(B) .We conduct comprehensive experiments investigating the exploration strategies for DQN under a multi-agent setting. For all the Q networks in our experiments, we use ReLU as our activation function. Given that all experiments are conducted under multi-agent settings unless explicitly specified as a single-agent or centralized scenario, we denote our methods: CoopTS-PHE as "PHE" and CoopTS-LMC as "LMC" in experimental contexts and figures. In addition to our methods, the baselines we selected are either commonly used (DQN [57] , DDQN [28] ) or with competitive empirical performance (Bootstrapped DQN [62] , NoisyNet DQN [26] ). We commence by presenting the comprehensive results for N = 25 in Figure 4 , illustrating that our randomized exploration methods exhibit greater suitability in realistic scenarios characterized by an increasing number of agents. This superiority is particularly evident under two potential circumstances: (1) where there are more limitations on computation or data access from each source in the real world, and (2) when parallel learning from multiple sources can significantly enhance runtime efficiency.BothSubsequently, we provide a more comprehensive study to investigate the exploration capabilities facilitated by parallel training. Preliminary experiments are conducted with a reduced state space, specifically considering N = 10. The study aims to investigate exploration capabilities across varying agent counts, specifically within the set m ∈ {1, 2, 3, 4}.We list the details of all swept hyper-parameters in N -chain for PHE and LMC in Table 2 and Table 3 respectively. Specifically, PHE is trained with reward noise ϵ k,l,n h = 10 -2 and regularizer noise ) and optimized by Adam SGLD [33] with α 1 = 0.9, α 2 = 0.999 and bias factor α = 0.1. The final hyper-parameters used in N -chain are presented in Table 4 .Performance Consistency with Varying m In the investigation detailed in Figure 5 , we explore parallel learning without inter-agent communication. Note that the x-axis implies the total training episodes from m agents. Consequently, while multiple agents engage in simultaneous policy learning, each agent independently formulates its policies without the exchange of transition information. The discernible trend in this scenario is that an increase in the number of agents sharing the total episodes results in a slower rate of policy learning. Notably, despite this temporal discrepancy, all learning trajectories eventually approximate convergence towards the optimal dashed line. To have a fair comparison among different synchronization conditions, we firstly record the empirical number of synchronization via linear condition in average, and then we consider constant value for constant condition and select proper base b for exponential condition with a similar number of synchronization. Figure 6 illustrates that any synchronization condition can improve learning efficiency but still with centralized learning as an upper bound. Note that the x-axis implies the total training episodes from m agents.Performance Compared with Bandit-inspired Methods Since one of our proposed random exploration strategies, PHE is a variant of approximation TS, it is fair for us to investigate the performance of other exploration methods from bandit algorithms with the integration of DQN. We mainly compare both TS and UCB under neural network (i.e., NeuralTS [90] and NeuralUCB [94] ) and linear (i.e., LinTS [5] and LinUCB [49] ) settings. We show that a performance gap exists between linear approaches and other neural-based methods even in a small-scale exploration problem with N = 10 in Figure 7 . Note that the x-axis implies the total training episodes from m agents. Computational Time We have demonstrated that both NeuralTS and NeuralUCB exhibit convergence to performance levels comparable to our proposed randomized exploration strategies (i.e., PHE and LMC) when considering the case of N = 10 with m = 4 under the synchronization condition (linear), as outlined in (3.3). However, we argue that the scalability of both methods is limited due to their associated computational costs. To substantiate this assertion, we conduct experiments across all methods including DQN baselines with N = 10 and m = 4 over 10 4 steps with varying neural network sizes, such as [32, 32, 32] , which signifies three layers with 32 neurons in each layer. Importantly, the length of the chain N has no bearing on the running time.In Figure 8 , we show the computational time of all methods under different neural network sizes. The solid lines represent the average computational time over 10 random seeds and the shaded area represents the standard deviation. We observe that NeuralTS and NeuralUCB have heavy running time consistently with varying network sizes. Although the computation time of LMC is still higher than other remaining approaches, we observe that it maintains a similar computation time with different neural network sizes, which can still be scaled up to more complex problems with larger neural networks. hyper-parameter tuning for the inverse temperature parameter β m,k in LMC, as illustrated in Figure 9 .It is crucial to note that the efficacy of learning is significantly influenced by the exploration capacity in both centralized learning and parallel learning without communication. Our observations reveal a discernible gap between centralized and parallel learning, a departure from the pattern observed in Figure 5 . We posit that the disparity may stem from issues associated with the replay buffer size in off-policy RL algorithms. Specifically, when the replay buffer exhausts its capacity for new transitions, the incoming transition replaces the oldest one.Hyper-parameter Tuning of Buffer Size Therefore, we present a performance comparison between a solitary agent (m = 1) and a scenario involving two agents (m = 2) in Figure 10 with different buffer sizes. Full buffer and half buffer indicate the replay buffer's capacity to store the complete set and half of the transitions during training, respectively. We observe that the learning process is more efficient with less buffer size in a centralized setting because having an excessively large replay buffer may potentially impede the efficiency of the learning process. Furthermore, the gap between centralized setting and paralleling learning still exists among different buffer sizes. Therefore, we focus on the setting of less buffer size with different synchronization conditions in Figure 11 . We conclude that linear condition results in competitive performance in both PHE and LMC in the N -chain problem and we report all exploration strategies with linear condition in Ablation Study of Sampling Mechanism To reduce the reward gap, we adopt a better sampling mechanism in the replay buffer with prioritized experience replay (PER). In Figure 12 , parallel learning without inter-agent communication can increase reward with PER, where the x-axis represents the total training episodes from m agents. However, centralized learning with PER improves faster convergence with similar performance and the trends for linear condition curves are similar. Therefore, the gap between centralized and parallel learning without communication is reduced with PER. Note that the main experimental results in Figure 1 are based on standard experience replay because standard sampling in linear condition has similar performance against PER with faster training time.While cooperative parallel learning enhances training efficiency through data sharing, challenges emerge when handling data from devices capturing images or audio due to privacy concerns in realworld applications. In response, our approach extends randomized exploration strategies to a federated reinforcement learning framework as shown in Algorithm 4, from Algorithm 1, which incorporates parameter synchronization among Q neural networks rather than relying on the conventional practice of sharing agents' transitions in Line 14 in Algorithm 4. Note that the synchronization follows the format as in Algorithm 1 to update Q functions with horizon h ∈ H. However, in practice, we can directly update the weight of the neural network to reduce the communication cost. The training process unfolds within a federated reinforcement learning framework, wherein local updates and global aggregations are iteratively executed [37] . Specifically, each agent iterates through multiple local updates of its value function, followed by server-mediated averaging of these functions across all agents, constituting a form of parameter sharing. Note that the transitions are not accessible among agents, leading us to directly synchronize all agents with parameter sharing every constant local iteration instead of synchronization condition in (3.3) . We use the same architecture for all the experiments in the Super Mario Bros task with the preprocessed images as the input states and 7 discrete actions in action space.Particularly, we construct 3 convolutional neural network layers with width [32, 64, 32] , followed by 2 fully connected layers with the output of action space in the Q network. The detailed hyper-parameters for Super Mario Bros task are presented in Table 5 . for agent m ∈ M do 3:Receive initial state s k m,1 .V k m,H+1 (•) ← 0. end if 20: end forBuildingEnv encompasses the regulation of heat flow in a multi-zone building to sustain a desired temperature setpoint. We focus on one pre-defined building called "office small" in different cities with varying weather types, i.e., Tampa (Hot Humid), Tucson (Hot Dry), Rochester (Cold Humid), and Great Falls (Cold Dry). Each episode is designed to span a single day, comprising 5-minute time intervals (H = 288, τ = 5/60 hours). Figure 14 : Evaluation performance at different cities in building energy systems Observation Space The state at time step t, denoted as s(t) ∈ R M +4 , encompasses the temperatures T i (t) of each zone, where i ∈ M , along with four additional properties: Q GHI (t), Qp (t), T G (t), and T E (t). Specifically, Q GHI (t) represents the heat gain from solar irradiance, Qp (t) denotes the heat acquired from occupant activities, while T G (t) and T E (t) signify the ground and outdoor environment temperatures, respectively.The continuous version of the action a(t) ∈ [-1, 1] M controls the heating of M zones. However, since our randomized exploration strategies use DQN [57] as the backbone, we adopt the multi-discrete action space defined in [85] , which is a vector of action spaces. Then we convert the multi-discrete action space to a single discrete action space with action mapping.Reward Function The primary objective is to minimize energy consumption while ensuring the maintenance of temperature within a specified comfort range. Therefore, the reward is penalized with both temperature deviations and HVAC energy consumption as follows:r(t) = -(1 -β)∥a(t)∥ 2 -β∥T target (t) -T (t)∥ 2 ,where T target (t) = [T target 1 (t), T target 2 (t), ..., T target M (t)] are the target temperatures and T ( t) = [T 1 (t), T 2 (t), ..., T M (t)] are the actual zonal temperatures. The parameter β is the trade-off between the energy consumption and temperature deviation penalties.We execute experiments following the united framework in Algorithm 1, synchronizing every constant number of steps across diverse weather conditions in varying cities. The hyper-parameters we used are in Table 6 . Subsequently, we evaluate the performance of all methods in distinct cities respectively, as illustrated in Figure 14 . Notably, our proposed random exploration strategies demonstrate a consistently higher mean return across all cities. However, it is worth highlighting that DQN in Figure 14 (c) and Noisy-Net in Figure 14 (d) exhibit lower returns compared to random actions. This outcome can be attributed to the discrete action space configuration [85] . In addition, we observe that maintaining thermal control of buildings is more challenging in cold weather conditions compared to hot weather conditions. 


Decision: This paper addresses randomized exploration in cooperative multi-agent reinforcement learning (MARL), focusing on parallel MDPs. The authors propose two Thompson Sampling (TS)-based algorithms, CoopTS-PHE and CoopTS-LMC, and provide theoretical guarantees regarding their regret bounds and communication complexity. The empirical results are validated through experiments on several benchmark environments, including a deep exploration problem, a video game, and a real-world energy systems task. The paper claims to make a significant contribution by providing the first theoretical results for randomized exploration in cooperative MARL.

Pros & Cons:

+ Unified algorithm framework for randomized exploration in parallel MDPs.
+ Theoretical guarantees for randomized exploration in cooperative MARL.
+ Extensive experiments across various environments.
+ Generally well-written.

- Limited Novelty: proposed algorithms are somewhat straightforward extensions of existing randomized exploration methods 
- The setting described in the paper could be more appropriately characterized as multi-task RL rather than multi-agent RL, as the transition and reward functions do not depend on the actions of other agents.
- The current work is heavily focused on linear MDPs, and the generalization to richer MDP classes is not well-explored.

In sum, considering the significant theoretical contributions, robust empirical validation, and the detailed clarifications provided in the rebuttal, I recommend accepting this paper.

Reviews: review: paper_summary: paper_summary: This paper investigates multi-agent reinforcement learning in cooperative scenarios. The main contribution is the extension of randomized exploration methods, including perturbed-history exploration and Langevin Monte Carlo exploration, to the multi-agent cooperative setting. The authors offer a regret analysis for the linear MDP case and present empirical results to validate the proposed method.
strength_weakness: strength_weakness: - About the contenders in experiments: It is unclear to me how the contenders DQN, Double DQN, and others were implemented. Are they running independently in multi-agent environments, with the average reward reported? If not, since Algorithm 1 provides a unified framework for parallel MDPs, the empirical comparison might be more complete if other contenders are also equipped with the synchronized steps. Besides, It is unclear why the performance of Bootstrapped DQN deteriorated significantly in the $N$-chain problem. 

- Discrepancy between theory and empirical results: As shown by Theorem 4.3 and Theorem 4.4, the average performance of the proposed method improves with the growth of $M$. However, in Figure 1 and Figure 4 in the appendix, a slower convergence rate is observed when $m$ is larger. Additionally, the scaling of the x-axis in Figure 1(a) and Figure 1(b) is different, which can be misleading since the convergence rate in Figure 1(b) is actually slower than in Figure 1(a).

- Parameter setting: It appears that setting the threshold $\gamma$ requires knowledge of $K$. How should this parameter be set in practice?

Overall, this paper makes solid progress in developing randomized algorithms for cooperative multi-agent RL. However, I am concerned about the discrepancy between theory and experiment. I would raise my score if these concerns are adequately addressed.
questions: questions: - Could you provide a more detailed explanation for the configuration of the contenders?
- Could you provide a more detailed explanation for the discrepancy between the theoretical guarantees and the experimental results?
- How should the parameter $\gamma$ be set in practice?
limitations: limitations: I do not find the negative societal impact of this work.
paper_summary: paper_summary: This paper considers randomized exploration in a multi-agent reinforcement learning setting called parallel MDPs. Two Thompson sampling-type algorithms are provided with a regret bound and communication complexity bound. The algorithms are empirically validated in multiple environments.
strength_weakness: strength_weakness: * The technical novelty and contribution seem limited. Can authors elaborate on the challenges in the analysis?
questions: questions: * What is the tradeoff between using perturbed history exploration and Langevin Monte Carlo exploration?
limitations: limitations: I didn't see potential negative societal impact of this work.
paper_summary: paper_summary: This paper studies provably efficient randomized exploration in parallel MDPs setting. The authors consider the linear setting, and propose two Thompson Sampling-style algorithms and establish the regret guarantees and communication cost. After that, they also conduct some experiments for evaluation.
strength_weakness: strength_weakness: 1. I'm not convinced that the setting considered in this paper should be called "multi-agent RL". I think it would be better to regard it as a multi-task RL setting (or maybe consider the terminology the authors used in paper: the "parallel MDP setting"), because the transition and reward functions for each agent here does not depend on the behavior of other agents, which I believe the key feature of MARL setting is missing.

2. The comparison with previous work is not precise and misleading:

    Line 210-211: "... matches the existing best single-agent results ...", which is not true. [1] considers a more general linear function approximation seeting and its regret only have $O(d)$ dependence on the dimension. I would also suggest to include the comparison with it in Table 1.

3. The setting requires more description. It seems to me there are two objectives: regret and communication complexity. It is unclear to me how the authors decide to trade-off them. I would suggest the authors to make it more clear. For the current version, it is unclear whether the regret bounds or the communication cost are optimized to optimal (or one of them are optimal while the other is better than previous).

    Besides, it seems that the agents can feel free to decide when to synchronize with the other agents to optimize the communication cost, which seems not practical in most of the times. 

4. The authors motivated the randomized exploration by pointing out that the UCB style algorithms can be computational intractable beyond the linear setting. However, the objective in Eq. (3.5) and update rule Eq.(3.7) seem not easy to be generalized beyond linear setting. Besides, all the theoretical results are also limited in the linear setting. So the motivation of this paper seems not convincing to me.


[1] Zanette et al., Learning Near Optimal Policies with Low Inherent Bellman Error
questions: questions: 1. Can you highlight a bit more about the technique novelty of the proposed methods?

2. In Page 26, line 877, can you explain in details why the inequality holds?

3. In Page 28, line 891, I didn't find the definition of $w^{1,0}, \hat{w}^{1,0}, \Lambda^1, b^1$ in Algorithm 3. Can you explain it?
limitations: limitations: N.A.
paper_summary: paper_summary: This paper presents the first result on provably efficient randomized exploration in cooperative multi-agent RL. This paper focuses on parallel MDP where the transition kernel assumes an approximately linear structure. To this end, two Thompson-sampling-type algorithms are propose which leverages the perturbed-history exploration and Langevin Monte Carlo exploration strategies, respectively. When applied to linear MDPs, both algorithms provaly achieve $\tilde{\mathcal{O}}(d^{3/2} H^2 \sqrt{MK})$ regret bound with $\tilde{\mathcal{O}} (d H M^2)$ communication complexity, where $H$ is the horizon length, $M$ is the number of agents and $d$ is the parameter dimension, marking the first-ever non-trivial theoretical results for randomized exploration in cooperative multi-agent RL. To evaluate the proposed methods, experiments on multiple parallel environments, including $N$-chain, a video game, and an energy system control problem, are conducted. The results show the effectiveness of the proposed algorithms, even under certain misspecified transitions.
strength_weakness: strength_weakness: I do not detect any technical or major weakness in the paper. I think this paper does make a novel theoretical contribution to a meaningful problem in RL. It is also well-written.
questions: questions: I do not have specific confusion regarding the major content of this paper since it is clearly written. Still I am interested in the following and any thoughts from the authors would be great.

This paper reports theoretical guarantees on linear MDPs. I am just wondering if randomized exploration in cooperative RL can be extended to richer MDP classes. It seems that the current algorithm design is very suitable for linear MDPs. However, the possibility and path of extending to other MDP classes is less clear.
limitations: limitations: Yes.

Comments: comment: Thank you very much for your positive feedback! We will add all these discussions to our final version.

Best,

Authors
Thanks for the detailed feedback. I do not have further questions and I will take the responses into consideration during the decision period.

I would suggest include the discussion regarding comparison with [3], trade-off between regret and communication complexity, and clarification on the synchronization framework during the paper revision.
Thank you very much for your further positive feedback! We will revise our paper according to your constructive reviews.

Best,

Authors
Dear authors,

Thank you for the response and insights on the extension beyond linear MDP! I have read all the reviews, and I will take all the reviews and responses into consideration during the discussion session among reviewers. I maintain my positive rating for the manuscript. I would suggest add the discussion on the extension beyond linear MDP and the technical novelty during the paper revision. 

Best,
Reviewer