Randomized Exploration in Cooperative Multi-Agent Reinforcement Learning
Authors: Hao-Lun Hsu
Weixin Wang
Miroslav Pajic
Pan Xu
Venue: NeurIPS 2024 poster (2024)
Keywords: Multi-Agent Reinforcement Learning
Randomized Exploration
Deep Reinforcement Learning
Primary area: reinforcement_learning
TL;DR: This paper presents the first study on provably efficient randomized exploration in cooperative multi-agent reinforcement learning.

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.

Randomized Exploration in Cooperative Multi-Agent Reinforcement Learning
Hao-Lun Hsu," Weixin Wang" Miroslav Pajic, Pan Xu
Duke University
(hao-lun hsu, weixin. miroslav pajic, sasic,pan, pan.paannn)................ xu] edu
Abstract
We present the first study on provably efficient randomized exploration in coopera- tive 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-bistory exploration (PHE) strategy and the Langevin Monte Carlo exploration (LMC) strategy respectively, which flexible in design and easy to implement in practice. For special class of parallel MDPs where the transition is (approximatelyy linear, theoretically prove that both CoopTS-PHE and CoopTS-LMC achieve (dd H regret bound with communication complexity M(HHM where di 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 multiple paralle! RL environments, includ- ing a deep exploration problem (i.e., N-chain), a video game, and 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, establish a connection between unified framework and the practical application of federated learning.
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 real- world systems [10, 25, 85]. This is particularly evident 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 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 strategies [27] and dynamic exploitation tacties [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, 55].
cooperative exploration
Optimism in the Face of Uncertainty (OFU) is a popular strategy to address the exploration- exploitation problem [1]. OFU strategy leads 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
Equal contribution.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

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 linear structure [18, 36). NeuralUCB is 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- -istorr 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 '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 advanceennts of randomized exploration in bandits and single-agent RL, there remains scarcity of research on randomized exploration within cooperative MARL, which motivates us to present the first investigation into provably efficient randomized exploration in cooperative MARI., 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 unified algorithm framework for learning parallel MDPs, and apply two TS-related strategies PHE and LMC for exploration, which leads to the CoopTTS-PHE and Coop'TS- algorithms. Unlike conventional TS, which suffers from sampling errors due to Laplace approxima- tion and expensive posterior computation [66, 46), our proposed algorithms only require adding standard Gaussian noises to the dataset (CoopTS-PHEE) or the gradient (CoopTS-LMMC) 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- -HE and CoopTS- LMC with linear function approximation can achieve a regret bound ( H2 (VIMy +
/ ()) with communication complexity Ö(dd + K/)) 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 y is parameter controlling the communication freeuuency When 7 ((/dMM, our algorithms attain Ō (22/2H2/MMK regret with Ö(d communication complexity. This result matches the best communication complexity in cooperative MARL [56], and the best regret bounds for randomized RI. 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 < = (Vd/MKK) the cumulative regret for CoopTS- -PEE matches the result in the linear homogeneous MDP setting. Simultaneously, when < = O (VI/MK), the cumulative regret for CoopTS-LMMC matches the result in the linear homogeneous MDP setting. This result indicates that CoopTT PHE has slightly higher tolerance on the model misspecification than CoopTS-LMM LMC. We conduct extensive experiments on various benchmarks with comprehensive ablation studies, including N- 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- Q-network

---

Table 1: Comparison on episodic, non-stationary, linear MDPs. We define the average regret 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.
Randomized Explocation
Generalizable Deep RL
Communication Complexity
Setting
Algoridhm
Regret
Average Regret
OPT-RLSVI [88]
Ö(dniv
Old VI/K)
X
single- agent
LSVI-UCH [36]
Ö(d5HP/K)
ŌaB H1/KK)
LSVI-PHE [32]
LMC-LSVI
Ō(di
4
LSVI-ASE [34]
OldHV/K)
OldH /1/K)
Coop-LSVI [24)
Oldi (1/MK)
X
X
dHMP
multi- agent
Asya-LSVI [56]
((d)
O /1/K))
X
X
dHM²
CoopTS-PHE (Ours)
Olah Ö(dH(PVMK)
V
dIMM
Coop TS-LMC (Ours)
(((HHA/MK)
O//F//1/MK)
dHM²
(DQN)-based baselines. We also show that these strategies in cooperative MARL can be adapted to the existing federated RL framework when data transitions are not shared.
2 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 E .,, the associated MDP is defined by the tuple MDP(S, AA, H, Pm, P rm). Here S and A are the state and action spaces respectively, H is the horizon length, I'm. (I ] and Ym = Jrm.AJhell
are the sets of transition kernels and reward functions. For step E [H], m, a) is the probability measure over the next state given current state-action pair (s, a). Fm.h S x A + [0, 1] is the deterministic reward function. The policy T. = mmm, hRe(M) is a sequences of decision rules where m, - A is the deterministic policy at step h.
For agent m E M, given any policy ı and transition P, to evaluate the policy effectiveness in the mh MDP, we define value function V (s) = E, 1E fmm, 0m, Sm,,h = s] and Q function 5m,A = 8, am,h = a] for any (h, 8, a) [H] x x A. Qm, (8, a) == Ex, (_# am, (mm.ar(5m.k (8m.h', (m,,
The optimal policy is defined as ny, and we denote (s) = ViT,i, (s). For each & E [K]. at the beginning of episode k; each agent
M receives the initial state sti chosen arbitrarily by the environment. For each step [H] in this episode, each agent m observes its current state st s selects an action att based on policy * receives a reward ( ahh,)) and then transitions the next state s hm, based on the transition probability measure PP,, (-Ist a..)) 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 as
Regret K) EmEm Σk [Vm (sh.)) (o
3 Algorithm Design
In this section, we first present unified algorithm framework for conducting randomized exploration in cooperative MARL. Then we introduce two practical randomized exploration strategies.
3.1 Unified Algorithm Framework
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, first define notations about the datasets stored on each agent's 's local machine and the server.
3

---

Algorithm Unified Algorithm Framework for Randomized Exploration in Parallel MDPs
1: Initialization: set [
(R), ( = 0.
2: for episode ..... K do
3: for agent m .M do
4: Receive initial state s
5: VE (m.H+1()) 1 O.
6:
{Q (.. Randomized Exploration for step h = L,..., do am < argmaXned Q (sth me a).
Algorithm Algorithm
7:
8:
9:
Receive sx 8m,411 and mm Une, (k)) <- Ungghe (k) U Us (s ak mihh bm1)
sh
if Condition then
12:
SYNCHRONIZE <- True. end if end for
14:
end for
16:
if SYNCHRONIZE, then
17:
for step h = H.... do
18:
V AAGNT:: Send Uhe (A) to SERVER.
SERVER: Uhe (k) + UMEM (men(k).
20:
SERVER: UN (k) &- (k) (k).
SERVER: Send UA (k) each AGENT.
AGENT: Set Ulec (k)) t- O.
23:
end for
24:
end if
25:
end for
Index notation We define (k) (denoted as k. when ambiguity arises) the last episode before episode & where synchronization happens. For episode k and step h, we define three datasets:
U. (I:) {5 Tn S (.r
(3.1a)
Uhee (k) (s Sn 6 sm,
) T=k++1'
k-1
(3.1b)
Un. A (k) UKT((K) Uu (k).
(3.1c)
By definition, (k)(()) is the dataset that is shared across all agents due to the latest synchronization at episode k, Ulic, (k) is the unique data collected by agent m since episode kg. Then Um, (k)) is the total dataset available for agent at the current time. Let K.(A)) = 1Um, (k:) be the total number of
data points. For the simplicity of notation, we also re-order the data points in Um. (k),, and rename
the tuple (8 " ho T (m.11) as (s', ,',"") such that we have (k) Ullk) (o', at, s!)). In fact, this can be done by the following one-to-one mapping
(T 1)M + T T kie (n, (M 1) + h, < k 1
(3.2)
Therefore, we use indices (s, (s,a,s') E (k) and E (IC(k)) interchangeably for the summation over set (k).
Algorithm interpretation At a high level, each episode l in Algorithm I consists of two stages. The first stage (Lines 3-15) is parallelly executed by all agents and the second stage (Lines 16-24) involves the communication among agents and the server.
In the first stage (Lines 3-15) of Algorithm 1, each agent operates in two parts. The first part (Line 6) updates estimated Q functions strategy (Algorithm Algorithm 3, which will introduced Section 3.2). In particular, given the estimated value functions V* (-)
through LSVI with randomized exploration
m Qt (:, a) step + 1, perform one step

---

robust backward Bellman update to obtain v at step h. And we initialize V #m. (-) 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 Qm,, and collect new data points which are added to the local dataset Un,, (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 is user-defined constant, which is easy to implement in practice.
(2) We can also synchronize at the episode of b',bb...... .......b b", with 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 feature mapping Φ(s, a) S x A + Rd, based on (3.1) I), we define the following empirical covariance matrices.
A Ls " Φ( 2 d 0 a p d')
loc A & m.h = Egy (a))e (0)
A mmh Net AA + loc A + AL.
We synchronize as long as the following condition is met:
del As + loc m.h + AI)
7
log
(3.3)
det (ser A, AI)
(k: k2)*
where 7 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 Uhe (k), i.e. the newly collected local data after the last synchronization, the server. Then, the server gathers all information together in U (k) and sends it back to each agent. Finally, each agent resets the local transition set U (k) < 0. Now agent m can access the dataset (k) UR (I)) U U (, (k)), which contains the historical data of all agents up to last synchronization and its local dataset.
3.2 Randomized Exploration Strategies
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", |f 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.
l==
We approximate the Q functions with the following function class F = {ff : SS A = f(w ((x, a))). where w E Rd is the parameter and Φ E Rdd is a feature mapping associated with state-action pairs. Now we define the loss function for estimating the Q functions.
K((k) ((r + Vk (*") ( d')) + A//w//? (h.n(w) = >/
(3.4)
where r/. rh (stssaa)) 0' = (ss', a'), and L is user-specified loss function.
Perturbed-History Exploration The first strategy we use in Algorithm is called the perturbed- history exploration [45, 47, 32), displayed in Algorithm 2. We refer to the resulting algorithm as CoopTS-PHEE In particular, we optimize the following randomized loss function, where we add random Gaussian noises to the rewards and regularizer in (3.4).
I (w)= = K(R) L [(rr, + Ch
d.n)) + Vh
m, (s") f ((: (')) + A|[w f
(3.5)
Addm lid where c
N(000²)) e/ ~ NO II),, and n E [N]. Then we obtain the following perturbed ~
estimated parameter
kn m.hh
argmin Imm (w).
(3.6)
5

---

Note that we repeat the above steps for 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 @ based on I Line 7 in Algorithm 2. Finally, by maximizing Q over action space A. we obtain the estimated value function V
Algorithm 2 Perturbed-History Exploration
1: Input: multi-sampling number N E N function class F (fw S A (s)
f(w; ((s, a)) }.
2: for step h H, 1 do
3: for n = 1, I,...NNo N do
4: Sample (<2.1in ]EEK(()) Lid N(00o²) and <x. NN(0, independently.
5: Solve knn m.h according to (3.6).
6: end for
7:
Q f min { max (Wwinii Φ). . h+
8: Vk (-) + max.EA Qm (:)).
9: end for
Output: (n (6)), Vk (3, 5h=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 with Algorithm leads to our second proposed algorithm, CoopTS-LMC. Specifically, we update the model parameter iteratively. For iterate j = 1,..., the update is given by
W
Rij.n m.h
R.j-1.m w m.h
1mm, V Lm (w w k.j- +
R.j. ( 21 m. m. m.h
(3.7)
where L is defined in (3.4), m,h E Rd is standard Gaussian noise, 7mm is the learning rate. and Bm., is the inverse temperature parameter. We similarly use the multi-sampling trick to obtain N independent estimators and estimate Q function O by truncation based on Line Algorithm
&jj.
Algorithm 3 Langevin Monte Carlo Exploration
I: Input: multi-sampling number N N function class F (fw S A Rl a) = f(w::((s,)) a))}. step sizes (mm. inverse temperature parameters
(Bm,k 1mm.kkmeAM MeM,,E((K]
2: for step h = H .... 1 do
3: for n = 1, N do
A:0.n
m.h --1,Je-11M
4:
w Wm.h
5: for j 1, I,., do
6: Sample kijn iid m.h N I).
7: Update w w.j. by (3.7).
k.j. m.k
8:
end for
9:
end for
Q f- min { maxpe[N] f( f(wtidh. :), H 11*
11: Vk m. (+) + max.EA (.,.(()a))))
12: end for
Output: t yk (c. ())))
Theoretical Analysis
4.1 Homogeneous Parallel Linear MDPs
provide theoretical analyses of our algorithms 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,r, is a linear MDP with feature map Φ: S x A - TR for any h E [H]. there exist d unknown measures f4y = (14))-.., an unknown vector 0 E Rd such that for any (s, a) E x A,
1a..----, (%) over S and
Pa(-1s, d) (Ø(s, a), pn
(n(8,a) (Ø(5, On)
Without loss of generality, we assume that for all (s,a) E S A. a)(s,a))l S 1 and max (S)) (0011) s vd.
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, is known that the Q-function admits linear form [36, Proposition 2.3]. Consequently, we choose the loss function L in (3.4) to be the (2 loss and approximate the Q function in the linear function class fw: Φ') = w TTd TT
Now we first present the regret bound for Coop
Theorem 4.2. Under Definition 4.1, choose L to be loss and linear function class f(w; Φ6) w 66 in (3.4). In CoopTS-PHE (Algorithm 1+Algorithm 2), let N Ö (og(()) log(co) where O(d) and cu = (1), (()) is the cumulative distribution function (CDF) of the standard normal distribution. Let and < 5 < 1. Under the determinant synchronization condition (3.3), we obtain the following cumulative regret
Regret (K) = (d) H2M (PPMMM(MMM dMy + VK)),
with probability at least 5. Remark 4.3. When we choose O(K/dM) in the synchronization condition (3.3), the cu- mulative regret of CoopTS-PHE becomes (d 2 H2 HK),, which matches the result of UCB exploration [24]. When M 1, the regret becomes (d3/2 H2 HK),), 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 Ö(M-d 3/2 HK). 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-LLMC.
Theorem 4.4. Under Definition 4.1, choose L to be l2 loss and linear function class f(w; Φ') w 8' in (3.4). In CoopTS-LMC (Algorithm ++Algorthhm 3), let N = C log( log(ch) where & 1- 1-2/2ee and C = (dd). Let 1/ V Bm,. ((H for all m M, = 1, and 0 < 8 < For any episode & E [K] and agent m E M, let the learning rate 7mm = 1/ 11/(44maxx (A (,,, update number Jn = 2n log(4H K d) where Ai Amax (A //min (A &A& m,hh) is the condition number of A m. Under the determinant synchronization condition (3.3), have
)) the
Regret (K) = (d) H H + +VK++)K))))))))))))))+)) VK)),
with probability at least 8.
Remark 4.5. Note that CoopTS-PHIP and CoopTS-LMC have the same order of regret. Hence the discussion in Remark 4.3 also applies to CoopTS-LLMC. We would also like to highlight that our results are the first rigorous regret bounds for randomized MARI. algorithms.
From the perspective of technical novelty, our analysis of randomized MARL algorithms different from that of -asBebased 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-LMCC and CoopTSS-PHL we use new e-covering technique to prove that the optimism lemma holds for all (s, a) E 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].
7

---

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 = Ō((d + K/))MH). 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 7 = ((K/dM) which only has a logarithmic dependence
the communication complexity reduces to the number of episodes K. Additionally, we provide a rigorous analysis to show that the algorithm only needs 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 (d H² K) with the communication complexity O(dHM) 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 cir- cumvent current communication by delaying it 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 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.
4.2 Misspecified Setting
In this part, we extend our theoretical analysis to the misspecified setting. In this setting, the transition functions Ph.. and the reward functions Tm,h are heterogeneous across different MDPs, which 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 Ç.
Definition 4.8 (Misspecified Parallel MDPs). For any 0 < S 1, and for any agent m M. the corresponding MDP(S, A, H... Fm) is a Ç-approximate linear MDP with feature map Φ: A Rd, for any h E [M]] there exist d unknown (signed) measures μt (p/ ,....,M (()) over S and an unknown vector 0, E RRd such that for any (s, a) E A, we have
(1)
P (- 18 a, - a), mn (-)) TV < S, (m,, (Ø(s, a) 0n)| S.
where || IV is the total variation norm, for two distributions P1 and Pz, define it as: ||P Pellrv = 2 Σxen (x) - P- Without loss of generality, we assume that | [ a)ll < 1 for all as A, and max (S)I,, |0O,1] }|} S Vd for all [4] and m E M.
Remark 4.9. Note that our misspecified setting defined in Definition 4.8 is 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 derive small heterogeneous setting from our misspecified setting, but not vice versa.
Next we state our regret bound for CoopTS-PHE in the misspecified setting.
Theorem 4.10 (Misspecified Regret Bound for CoopTS-PHE), In CoopTS-PHE (Algorithm 1+A1- gorithm 2), under Definition 4.8 and determinant synchronization condition (3.3), with the same initialization with Theorem 4.2, we obtain the following cumulative regret
Regret(K) 5( ( H2 H2 (v dMy VK)
dH M
MHH ( dMM+ +VK))).
with probability at least 8.
Remark 4.11. When we choose < = o OVd/MMK) the cumulative regret becomes (dd) H² / + vK)). This matches the result of Theorem 4.2 in the linear MDP setting.
Similarly, have the following result for C--MTS-LMC.
8

---

Theorem 4.12 (Misspecified Regret Bound for CoopTS-LMMC), In CoopTS-LLMC (Algorithm 1+Al-
gorithm 3), under Definition 4.8 and determinant synchronization condition (3.3), with the same initialization with Theorem 4.4 except that 1/ O(HVd + H H...MKK MdC)). we obtain the following cumulative regret
Regret(Ki = 3 MM VK) + di HV (V VK)C).
with probability at least 6.
Remark 4.13. When Ç ( (D((V1 WIMM)........... the eumulative regret becomes Ō H² VM (VaMy V.)). This matches the result of Theorem 4.4 in the linear MDP setting. By comparing Theo- rems 4.10 and 4., we find the result of Co-PTS-LMC has an extra v factor worse than that of CooPTS-PHE, causing the chosen in CoopTS has an extra vd order over that in CoopTS-LMC. This indicates that CoopTS-PHE has better performance tolerance for the misspecified setting.
Experiments
In this section, we present empirical evaluation of our proposed randomized exploration strategies (i.e., CoopTS- PHE and CoopTS-LMG with deep Q --etwworks (DQNs) [57] as the core algorithm 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 single-agent centralized scenario, denote CoopTSS-PEE as "PHE" and CoopT'S-LMC as "LMC" both experimental contexts and figures. Note that
all our experiments Nvidia RTX A,5000 with 24GB RAM. The implementation of this work can be found at http:///tub..om//pxxlul/////ee/e
Epioote thekum mm
UCC
Rocial DCt
1990
2013
Training
(a) m=2
(b) m=3
(c) Mario (Parallel)
(d) Mario (Federated)
Figure Comparison among different exploration strategies in different environments. (a)-(b): N- with N 25. (c)-(d): Super Mario Bros. All results are averaged over 10 runs and the shaded area represents the standard deviation.
5.1
N-chain
The N N-chain [62] comprises a sequence of N states denoted as {st Assuming the existence of m agents, all initiating their trajectories from $2, this study explores the dynamics their movement within the chain. At each time step, agents face the decision to move either left or right. Notably, each agent incurs nominal reward of r 0.001 upon reaching state 51, while more substantial reward of r is obtained upon reaching the terminal state sN. The illustration of N- environment shown in Appendix K.1. With horizon length N the optimal return is 10. We consider N 25 with the communication among agents in Figure following the synchronization approach Algorithm In Figure ((a), we show that PHE and Bootstrapped DQN result in higher average episode return among all agents while LMC can also eventually converge to similar reward.
Upon increasing the number of agents exploration methods outperform all other baselines. Notably, the fluctuation in PHE is observed to be less pronounced against LMC. This observation lends support 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.
3, show in Figure 1(b) that randomized
5.2 Super Mario Bros
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 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 I(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 ((a) and 1(b). In the case of PHE, Gaussian noise 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, is crucial 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 proposed method to federated learning shown in Figure ((d) with details in Appendix K.2.
5.3 Thermal Control of Building Energy Systems
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]. BuildingEny designed to manage the heating supply in a multi-zone building, which involves addressing real- world 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 Al- gorithm for each exploration strategy. During the evaluation, we deploy those trained policies to the environment of cach city/weather respectively. We include all methods as well as random action Fig- ure 2 for a fair comparison. Specifically, we sample action randomly from action space for random action. We display the distribution of the return with proba- bility density in violin plots, indicating that our PHE and LMC can perform better with a higher mean. Additional results for other cities can found in Appendix K.3.
-50
Randam
PIE
UNC
DON Donntnspeettll//eee Met
DOCK
Figure 2: Evaluation performance at Tampa (hot humid) in building energy systems. All results are averaged over 10 runs.
6 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: Coop'TS-PHF and CS 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 CS-MTS.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 catmuuiiaaionefffiiiieeee algorithm to reduce the substantial communication costs in the general function class setting is another potential direction.
10

---

Acknowledgments
We would like to thank the anonymous reviewers for their helpful comments. HH and MP were supported in part by the ONR under agreement N00014-23-1-2266, AFOSR under the award number FA9550-19- 19-1-11-9------- and by the NSF under NAIAD Award 2332744 as well as the National AI Institute for Edge Computing Leveraging Next Generation Wireless Networks, Grant CNS-21 12562. WW and PX were supported in part by the National Science Foundation (DMS-2323) MMMS-2323112 12) and the Whitehead Scholars Program at the Duke University School of Medicine. The views and conclusions this paper are those of the authors and should not interpreted as representing any funding agency.
References
[1] Y. Abbasi-Yadkann D. Pál, and C. Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011. 1, 56, 57
[2] M. Abeille and A. Lazaric. Linear thompson sampling revisited. In Artificial Intelligence and Statistics, pages 176-188 184. PMLR, 2017. 18
[3] M. Abramowitz and I. A. Stegun. Handbook of mathematical functions with formulas, graphs, and mathematical tables, volume 55. US Government printing office, 1968. 57
[4] Agrawal, Chen, and N. Jiang. Improved worst-case regret bounds for randomized least- squares value iteration. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 6566-6573, 2021. 17
[5] S. Agrawal and N. Goyal. Thompson sampling for contextual bandits with linear payoffs. In International Conference Machine Learning, pages 127-135, 2013. 60
[6] S. Agrawal and N. Goyal. Thompson sampling for contextual bandits with linear payoffs. In International conference on machine learning, pages 127-135. PMLR, 2013. 18
[7] Agrawal and R. Jia. Optimistic posterior sampling for reinforcement learning: worst-case regret bounds. In Advances in Neural Information Processing Systems, volume 30, pages 1184-1 1194, 2017. 2, 17
[8] D. Bakry, I. Gentil, M. Ledoux, et al. Analysis and geometry of Markov diffusion operators, volume 103. Springer, 2014. 6
[9] N. A. Bakshi, T. Gupta. R. Ghods, and J. Schneider. Guts: Generalized uncertainty-awant thompson sampling for multi-agent active search. IEEE International Conference on Robotics and Automation (ICRA), pages 7735-7741. IEEE, 2023. 17
[10] A. L. Bazzan. Opportunities for multiagent systems and multiagent reinforcement learning in traffic control. Aulonomous Agents and Multi-Agent Systems, 18:342-375, 2009.
[11] D. S. Bernstein, R. Givan, N. Immerman, and S. Zilberstein. The complexity of decentralized control of markov decision processes. Mathematics of Operations Research, 27(4):819-84) 2002. 17
[12] C. Boutilier. Planning, learning and coordination in multiagent decision processes. In Theoreti- cal Aspects of Rationality and Knowledge, 1996. 17
[13] Q. Cai, Z. Yang, C. Jin, and Z. Wang. Provably efficient exploration in policy optimization. In International Conference Machine Learning, pages 1283-1294 PMLR, 2020. 7, 22
[14] G. Chalkiadakis and C. Boutilier. Coordination in multiagent reinforcement learning: A bayesian approach. In Proceedings of the second international joint conference on Autonomous agents and multiagent systems, pages 709-716, 2003.
[15] J. Chan, A. Pacchiano, N. Tripuraneni, Y. S. Song, P. Bartlett, and M. Jordan. Parallelizing contextual bandits. arXiv preprint arXiv:2105. 10590, 2021.
[16] O. Chapelle and L. Li. An empirical evaluation of thompson sampling. Advances neural information processing systems, 24, 2011. 5, 18

---

[17] Y. Chen, P. Dong, Q. Bai. M. Dimakopoulou, W. Xu, and Z. Zhou. Society of agents: Regret bounds of concurrent thompson sampling, Advances in Neural Information Processing Systems, pages 7587-7598, 2022. 17
[18] W. Chu, L. Li, L. Reyzin, and R. Schapire. Contextual bandits with linear payoff functions, In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pages 204.214. JMLR Workshop and Conference Proceedings, 2011. 1,2
[19] A. S. Dalalyan. Theoretical guarantees for approximate sampling from smooth and log-concave densities. Journal of the Royal Statistical Society Series B: Statistical Methodology. 79(3): 651-676, 2017.
[20] C. Dann, M. Mohri, T. Zhang, and Zimmert, A provably efficient model-free posterior sam- pling method for episodic reinforcement learning, Advances in neural information processing systems, 34, 2021. 17
[21] M. Dimakopoulou and B. V. Roy. Coordinated exploration in concurrent reinforcement learning. Proceedings of the 35th International Conference on Machine Learning, pages 1271-1279, 2018.
[22] M. Dimakopoulou, I. Osband, and B. V. Roy. Scalable coordinated exploration in concurrent reinforcement learning. Advances in Neural Information Processing Systems, pages 4219-4227, 2018.
[23] G. Ding, J. Koh, K. Merckaert, B. Vanderborght, M. M. Nicotra, C. Heckman, A. Roncone, and I.. Chen. Distributed reinforcement learning for cooperative multi-rohot object manipulation. In Proceedings of the 2020 International Conference on Autonomous Agents and Multiagent Systems, AAMAS, pages 1831-1833. ACM, 2020.
[24] A. Dubey and A. Pentland. Provably efficient cooperative multi-agent reinforcement learning with function approximation. arXiv preprint arXiv:2103.04977 2021. 1, 3, 7, 8, 17, 19, 22
[25] Y. Fei and R. Xu. Cascaded gaps: Towards logarithmic regret for risk-sensitive reinforcement learning. In International Conference on Machine Learning, pages 6392-6417. PMLR, 2022. 1
[26] M. Fortunato, M. G. Azar, B. Piot, et al. Noisy networks for exploration. In International Conference on Learning Representations, 2018. 9, 17, 58
[27] J. Hao, T. Yang, H. Tang, C. Bai, J. Liu, Z. Meng, P. Liu, and Z. Wang. Exploration in deep reinforcement learning: From single-agent multiagent domain. IEEE Transactions on Neural Networks and Learning Systems, 2023.
[28] H. V. Hasselt, A. Guez, and D. Silver. Deep reinforcement learning with double qlearning. In Annual AAAI Conference Artificial Intelligence (AAAT), 2016. 9, 58
[29] F. Hillel, 7. S. Karnin, T. Koren, R. Lempel, and O. Somekh. Distributed exploration in multi-armed bandits. Advances in Neural Information Processing Systems, 26, 2013. 17
[30] R. A. Horn and C. R. Johnson. Matrix analysis. Cambridge university press, 2012. 56
[31] T. Huix, M. Zhang, and A. Durmus. Tight regret and complexity bounds for thompson sampling via langevin monte carlo. In F. Ruiz, Dy, and J.-W. van de Meent, editors, Proceedings of 26th International Conference on Artificial Intelligence and Statisties, volume 206 of Proceedings of Machine Learning Research, pages 8749-8770. PMLR, 25-27 Apr 2023. URL attps://procedt
www.:mww......a..mmmmmmmmmmm..ee mlr press/ wvtesss//vv/////// https//////////x22...mm2 http//uiiii.a...... html. 2
[32] H. Ishfaq, Q. Cui, V. Nguyen, A. Ayoub, Z. Yang. Z. Wang, D. Precup, and L. Yang. Ran- domized exploration in reinforeement learning with general value function approximation. In International Conference Machine Learning, pages 4607-4616. PMLR, 2021. 2, 10, 17,56, 56, 57
[33] H. Ishfaq, Q. Lan, P. Xu, A. R. Mahmood, D. Precup, A. Anandkumar, and K. Azizzadenesheli Provable and practical: Efficient exploration in reinforcement learning via langevin monte carlo. In The Twelfth International Conference on Learning Representations, 2024. URL https:/ //op///peeeeieeee///e/ee httpp//eeeeee..eeefoorooeeeeeeee
2, 6, 7, 10, 17, 26, 59
12

---

[34] H. Ishfaq, Y. Tan, Y. Yang, Q. Lan, J. Lu, A. R. Mahmood, D. Precup, and P. Xu. More efficient randomized exploration for reinforcement learning via approximate sampling. Reinforcement Learning Journal, 3:121 1-1235, 2024. 2,
[35] M. Jahamia-Jahromi, R. Jain, and A. Nayyar. A bayesian learning algorithm for unknown zero-sum stochastic games with arbitrary opponent. In International Conference on Artificial Intelligence and Statistics, pages 3880-3888. PMLR, 2024. 17
[36] C. Jin, Z. Yang, Z. Wang, and M. I. Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pages 2137-2143. PMLR, 2020. 1, 2, 7, 8, 17, 56
[37] H. Jin, Y. Peng, W. Yang, S. Wang, and Z. Zhang. Federated reinforcement learning with environment heterogeneity. In International Conference on Artificial Intelligence and Statistics, pages 18 37. PMLR, 2022. 64
[38] T. Jin, P. Xu, J. Shi, X. Xiao, and Q. Gu. Mots: Minimax optimal thompson sampling. In International Conference on Machine Learning, pages 5074-5083. PMLR, 2021. 17
[39] T. Jin, P. Xu, X. Xiao, and A. Anandkumar. Finite-time regret of thompson sampling algorithms for exponential family multi-armed bandits. Advances in Neural Information Processing Systems, 55:38475-38435 2022.
[40] T. Jin, X. Yang, X. Xiao, and P. Xu. Thompson sampling with less exploration is fast and optimal. In International Conference on Machine Learning, pages 15239-15261. PMLR, 2023. 17
[41] T. Jin, H.-L. Hsu, W. Chang, and Xu. Finite-time frequentist regret bounds of multi-agent thompson sampling on sparse hypergraphs. In Annual AAAI Conference on Artificial Intelligence (AAAI), 2024.11 17
[42] A. Karbasi, N. L. Kuang, Y. Ma, and S. Mitra. Langevin thompson sampling with logarithmic communication: Bandits and reinforcement learning. In A. Krause, E. Brunskill, K. Cho, B. Engelhardt, S. Sabato, and J. Scarlett, editors, Proceedings of the 40th International Con- ference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 15828-15860. PMLR, 23-29 Jul 2023. URL https: httts:://proeeeeee http///peeeeen...e//ee////e/s.ee mlr. .presa/ +202/karbas www.aaaaaaaaaaaaaaaaaaaaaaaaaaaa html. 2, 17
[43] R. M. Kretchmar. Parallel reinforcement learning. The 6th World Conference on Systemics, Cybernetics, and Informatics, 2002. 17
[44] N. Kuang, M. Yin, et al. Posterior sampling with delayed feedback for reinforcement learning with linear function approximation. Advances in neural information processing systems, 2023.
17
[45] B. Kveton, Szepesvari, M. Ghavamzadeh, and C. Boutilier. Perturbed-histon exploration in stochastic multi-armes bandits, 2019. 2,
[46] B. Kveton, M. Zaheer, C. Szepesvari, L. Li, M. Ghavamzadeh, and C. Boutilier. Randomized exploration in generalized linear bandits. In International Conference Artificial Intelligence and Statistics, pages 2066-2076. PMLR, 2020. 2, 18
[47] B. Kveton, M. Zaheer, C. Szepesvari, L. Li, M. Ghavamzadeh, and C. Boutilier. Randomized exploration in generalized linear bandits. In S. Chiappa and R. Calandra, editors, Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pages 2066-2076. PMLR, 26-28 Aug 2020.
URL https: : httppp:://proooe http///pceeennnse////eeee/eess/e mlr. wrw.sprssssseeee vvtss/v11/////// www.///vetvvoiaa wwt.//eett.aaaaaam html. 2.5
[48] P. Landgren, V. Srivastava, and N. E. Leonard. On distributed cooperative decision-making in multiarmed bandits. In 2016 European Control Conference (ECC), pages 243-248. IEFE, 2016.
17
13

---

[49] L. Li, W. Chu, J. Langford. and R. E. Schapire. A contextual- approach to personalized news article recommendation. In Proceedings of the 19th international conference on World wide web, pages 661-670 2010. 60
[50] L. Li, Y. Lu, and D. Zhou. Provably optimal algorithms for generalized linear contextual bandits. In International Conference on Machine Learning, pages 2071 1-2000. PMLR, 2017.
[51] T. Li, A. K. Sahu, M. Zaheer, M. Sanjabi, A. Talwalkar, and V. Smith. Federated optimization in heterogeneous networks. In Proceedings of Machine Learning and Systems, volume 2, pages 429-450, 2020. 17
[52] Z. Li, Y. Li, Y. Zhang. T. Zhang, and Z.-Q. Luo. Hyperdqn: A randomized exploration method for deep reinforeement learning. In International Conference on Learning Representations, 2022. 17
[53] J. Lidard, U. Madhushani, and N. E. Leonard. Provably efficient multi-agent reinforcement learning with fully decentralized communication. In 2022 American Control Conference (ACC), pages 3311-3316. IEEE, 2022. 17
[54] B. Liu, L. Wang, and M. Liu. Lifelong federated reinforcement learning: a learning architecture for navigation in cloud robotic systems. IEFE Robotics and Automation Letters, 4(4):4555 4562, 2019.
[55] Z. Liu, J. Zhang, Z. Liu, H. Du, Z. Wang, D. Niyato, M. Guizani, and B. Ai. Cell-free xl-mimo meets multi-agent reinforcement learning: Architectures, challenges, and future directions. IEEE Wireless Communications, 31(4):155-162, 2024. 1
[56) Y. Min, He, Wang, and Q. Gu. Cooperative multi-agent reinforcement learning: asyn- chronous communication and linear function approximation. In International Conference on Machine Learning, pages 24785-24811. PMLR, 2023. 1, 3, 8, 17
[57] V. Mnih, K. Kavukcuoglu, D. Silver, et al. Human-level control through deep reinforcement learning. Nature, 518:529-533, 2015. 58, 65
[58] A. Mousavi-Hosseini,, T. Farghly, Y. He, K. Balasubramanian, and M. A. Erdogdu. Towards complete analysis of langevin monte carlo: Beyond poincaré inequality, 2023. 2
[59] T. Nguyen- Tang and R. Arora. On sample-effcieen offline reinforcement learning: Data diversity, posterior sampling and beyond. Advances neural information processing systems, 2023. 17
[60] I. Osband and B. Van Roy. Why is posterior sampling better than optimism for reinforcement learning? In International conference machine learming, pages 2701-2710, PMLR, 2017. 2, 5, 17
[61] I. Osband, D. Russo, and B. Van Roy. (more) efficient reinforcement learning via posterior sampling. Advances in Neural Information Processing Systems, 26, 2013. 2, 5, 17
[62] Osband, C. Blundell, A. Pritzel, and B. V. Roy. Deep exploration via bootstrapped dqn. Advances in neural information processing systems, 29, 2016. 9, 17,58
[63] I. Osband, B. Van Roy, and Z. Wen. Generalization and exploration via randomized value functions. In International Conference on Machine Learning, pages 2377-2386. PMLR, 2016.
17
[64] I. Osband, J. Aslanides, and A. Cassirer. Randomized prior functions for deep reinforcement learning. Advances in neural information processing systems, 31, 2018. 17
[65] S. Qiu, Z. Dai, H. Zhong, Z. Wang, Z. Yang. and T. Zhang. Posterior sampling for competitive rl: Function approximation and partial observation. Advances in neural information processing systems, 2023. 17
[66] C. Riquelme, G. Tucker, and J. Snoek. Deep bayesian bandits showdown: An empirical comparison of bayesian deep networks for thompson sampling. In International Conference on Learning Representations, 2018. 2, 18
14

---

[67] G. O. Roberts and R. L. Tweedie. Exponential convergence of langevin distributions and their discrete approximations. Bernoulli, pages 341-363, 1996. 6
[68] C. Rojas- Córdov, A. J. Williamson, J. A. Pertuze, and G. Calvo. Why one strategy does not fit all: a systematic review on exploration-exploitaiio in different organizational archetypes. Review of Managerial Science, 17(7):2251-2295 2023. 1
[69] Y. Ruan, J. Yang, and Y. Zhou. Linear bandits with limited adaptivity and learning distributional optimal design. Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 74-87, 2021. 7
[70] D. Russo. Worst-case regret bounds for exploration via randomized value functions. Advances in neural information processing systems, 32:1 12:14400-14420 2019. 17
[71] M. Strens. A bayesian framework for reinforcement learning. In International Conference Machine Learning, pages 943-950. PMLR, 2000. 17
[72] M. E. Taylor and P. Stone. Transfer learning for reinforcement learning domains: survey. Journal of Machine Learning Research, 10356):1633-168) 2009. 17
[73] W. R. Thompson. On the likelihood that one unknown probability exceeds another view of the evidence of two samples. Biometrika, 25(3-4))285-29)) 1933. 2, 17
[74] J.-J. Tsay, C.-C. Chen, and J.-J. Hsu. Evolving intelligent mario controller by reinforcement learning. In International Conference on Technologies and Applications of Artificial Intelligence. pages 266-272, 2011. 1, 10
[75] R. Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018. 56
[76] R. Wang. R. R. Salakhutdinov, and L. Yang. Reinforcement learning with general value function approximation: Provably efficient approach via bounded eluder dimension. Advances in Neural Information Processing Systems, 33:6123-6133 2020. 1,2
[77] Y. Wang. J. Hu, X. Chen, and L. Wang. Distributed bandit learning: Near-optimal regret with efficient communication. In International Conference on Learning Representations, 2020. 17
[78] Z. Wang and M. Zhou. Thompson sampling via local uncertainty. In International Conference on Machine Learning, pages 10115-10125. PMLR, 2020. 17
[79] Q. Xie, Y. Chen, Z. Wang, and Z. Yang. Learning zero-sum simultancous- move markov games using function approximation and correlated equilibrium. In Proceedings of Thirty Third Conference Learning Theory, volume 125, pages 3674-3682. PMLR, 2020. 17
[80] W. Xiong, H. Zhong, C. Shi, C. Shen, and T. Zhang. A self-play posterior sampling algorithm for zero-sum markov games. International Conference on Machine Learning, pages 24496- 24523. PMLR, 2022. 17
[81] Xu, J. Chen, D. Zou, and Q. Gu. Global convergence of langevin dynamics based algorithms for nonconvex optimization. Advances in Neural Information Processing Systems, 31, 2018. 6
[82] P. Xu, Z. Wen, H. Zhao, and Q. Gu. Neural contextual bandits with deep representation and shallow exploration. In International Conference on Learning Representations, 2021.
[83] P. Xu, H. Zheng, E. V. Mazumdar, K. Azizzadenesheli, and A. Anandkumar. Langevin monte carlo for contextual bandits. In International Conference on Machine Learning, pages 24830- 24850. PMLR, 2022. 2, 6, 17, 18
[84] D. Ye, G. Chen, W. Zhang, S. Chen, B. Yuan, B. Liu, J. Chen, Z. Liu, F. Qiu, H. Yu, et al. Towards playing full moba games with deep reinforcement learning. Advances in Neural Information Processing Systems, 33:621-632, 2020.
15

---

[85] C. Yeh, V. Li. R. Datta, J. Arroyo, N. Christianson, C. Zhang, Y. Chen, M. Hosseini, A. Golmo- hammadi, Shi. Y. Yue, and A. Wierman. Sustaingym: benchmark suite of reinforcement learning for sustainability applications. In Thirty-seventh Conference on Neural Information Processing Systems Datasets and Benchmarks Track. PMLR, 2023. 10, 65, 66
[86] C. Yu, A. Velu, E. Vinitsky, J. Gao, Y. Wang, A. Bayen, and Y. Wu. The surprising effectiveness of PPO in cooperative multi-agent games. In Thirty-sixth Conference Neural Information Processing Systems Datasets and Benchmarks Track, 2022. 17
[87] C. Yu, X. Yang, J. Gao, J. Chen, Y. Li, J. Liu, Y. Xiang, R. Huang, H. Yang, Y. Wu, and Y. Wang- Asynchronous multi-agent reinforcement learning for efficient real-time multi-robot cooperative exploration. In Proceedings of the 2023 International Conference on Autonomous A Agents and Multiagent Systems, AAMAS, pages 1107-1115. ACM, 2023. 17
[88] A. Zanette, D. Brandfonbrener, E. Brunskill, M. Pirotta, and A. Lazaric. Frequentist regret bounds for randomized least-squares value iteration. In International Conference on Artificial Intelligence and Statistics, pages 1954-1964. PMLR, 2020. 3, 17
rellii-agetrinnnforeeemme [89] K. Zhang, Z. Yang, H. Liu, T. Zhang, and Başar. Fully decentralized multi-agent reinforcement learning with networked agents. In International Conference on Machine Learning, volume 80, pages 5872 1872-5881. PMLR, 2018. 17
[90] W. Zhang, D. Zhou, L. Li, and Q. Gu. Neural thompson sampling. In International Conference on Learning Representations, 2021. 60
[91] Y. Zhang. G. Qu, P. Xu, Y. Lin, Z. Chen, and A. Wierman. Global convergence of localized policy iteration in networked multi-agent reinforcement learning. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 7(1):1-51, 2023. 17
[92] Y. Zhao, I. Borovikov, J. Rupert, C. Somers, and A. Beirami. On multi-agent learning in team sports games. arXiv preprint arXiv: 1906. 10/24, 2019.
[93] H. Zhong and T. Zhang. A theoretical analysis of optimistic proximal policy optimization in linear markov decision processes. Advances in Neural Information Processing Systems, 36, 2023.
[94] D. Zhou, L. Li, and Q. Gu. Neural contextual bandits with ucb-based exploration. In Interna- tional Conference on Machine Learning, pages 1192-115502 2020. 2, 60
[95] Y. Zhou, J. Li, and J. Zhu. Posterior sampling for multi-agent reinforcement learning: solv- ing extensive games with imperfect information. In International Conference on Learning Representations, 2019. 2, 17
[96] D. Zou, P. Xu, and Q Gu. Faster convergence of stochastic gradient langevin dynamics for con-log-concave sampling. In Uncertainty in Artificial Intelligence, pages 1152-1162, PMLR, 2021. 6
16

---

A Related Work
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 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 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 heterogeneous federated learning [51] and exhibit improved generalizability in transfer learning scenarios [72].
We focus parallel MDPs in this paper, where agents interact with the environment simultancously to tackle shared challenges within extensive and distributed systems [43]. Recently, Dubey and Pentland [24] proposed the Coop-LSSV algorithm, extending the LSVV-UCB algorithm [36] in single- agent 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, 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 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.
Randomized Exploration The roots of randomized exploration, particularly TS, can be traced back 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-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 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, Randomized perturbations to approximate the posterior, with frequentist regret analysis applied under the tabular MDP setting [63], inspiring subsequent works focusing theoretical analyses aimed at improving worst-case regret under tabular MDPs [70, 4], with extensions to the linear setting [88, 32, 20J. 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].
Value Iteration (RLSVI) is an approach that leverages random
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, 65J. There is no existing work studying randomized exploration for cooperative multi-agent settings.
17

---

B Instantiation of the Proposed Algorithms in the Linear Function Class
In this section, we specifically discuss 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 choose L to be lp loss and linear function class fww Φ = w Φ' By solving this least-square regression problem, we obtain the unperturbed regression estimator w m.k" In the linear setting, we have the closed-form solution
m.h (A -
b mm,h
(B.1)
where A m. and b a defined as follows
K((k
k m.h
Σ
Φ a' (s) + AI.
=
X((M)
b
[mn(st,c + vk mmh+1 (8 (d)))'(',
m.h
A natural way of doing randomized exploration is to add noise (A ( to with m.h and get the estimated parameter w Wm. Then we can construct estimated Q function (+:)) min( w m. H h + 1]t. 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 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 to the squared loss. By solving this least-square regression problem, we obtain the perturbed regression estimator w in CoopTS The following proposition conveys that CoopTS-PHE is actually equivalent to CoopTS.
Proposition B.1 (Equivalent to CoopTS), The output w m,h by CoopTS-PHIE is equivalent to adding
a Gaussian vector to the unperturbed regression estimator W mm i.e. wh.n w m.h h + Sm,, where ckin o'
For CooPTS-LMC (Algorithm ++Algori 3), let function approximation in (3.4) be linear and choose L to be lz loss to get the loss function. Then after finishing the LMC update, we get the estimated parameter w k.Ju." and construct the model approximation of Q function. The following k.J.
mih proposition conveys that the distribution of wmih converges to the posterior distribution of Thompson mih Sampling exploration. The proof of this proposition is given in [83].
Proposition B.2 (Approximately equivalent to CoopTS [83]). If the epoch length Js in Al- gorithm 3 is sufficiently large, the distribution of w mmh converges to Gaussian distribution ((w " pm. (A mn
Propositions B.1 and B.2 indicate that the results of our two randomized exploration strategies are closely related CoopTS. As we have mentioned above, in CoopTS. the estimated parameter However, in practice, this NOO, I) first, then we calculate w M..
w- is sampled from the normal distribution A (w A. o² a (Am,k)
sampling often executed in this way: sample
wek m. + - and obtain the estimated parameter. Nevertheless, computing (A can be computationally expensive, often requiring at least ((d²) operations with the Cholesky decomposition, making impractical for high- digh-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, pointed out by recent work [16, 66, 46, 83], the Laplace approximation- Thompson Sampling exhibits constant approximation error in the estimation of the posterior distribution. Therefore, it necessitates careful redesign of the covariance matrix to ensure effective performance.
18

---

Advantages of PHE and LMC As mentioned above, computing (A can be computationally expensive. However, ceturbbed-Histor 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 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 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 implement practice.
Communication cost 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 met, the agents will only need to send their calculated local statistics loc A m and "eb"" m.... to help solve the regression problem. This communication cost is much smaller because A is only a ddx d matrix and b is only 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 the collected estimated Q functions. which can largely reduce the communication cost.
C Analysis of the Communication Complexity of Algorithm! 1
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(HHM²), in contrast with the OdH MS 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 o = foi...., Fn as the synchronization episodes, where ag E [K], we also denote dg To bound the number of synchronization n, we separate a into two parts with an undetermined term
11 (i E [n]la, 0i-1 S sa)
1 (i E [n]lo; 01- > a}.
Then have n [1| + [T2/. Note that
K 2 on = Σ (a-0011))
E(o, (a. - 01-1) > 12//a
ieh
Then we have [Z2| < K/a. Then note that
det(A mi.h)
det 0: det(A
log
log
det( A
01-11
(1-11
Σ
7
σi 0i-1
ich
Y
2 11
(C.I)
Define AK hand, we have
EmEm Ek ((ste, ((
+ AI where 2/, = (s am..) On the other
det(A 42 (m,)))
det det(Agg) (A mik
log
= log
det( (
det A 00 ka,h)
19

---

dct(AA)
$ log
det((A))
S dog MKKd),
(C.2)
where the first inequality holds due to the trivial fact that A B = det(A) det(BB, the second inequality follow from Lemma J.2 and the fact that ||<((-) ll S 1. Combine (C.1) and (C.2), then we have [1] S da/7 log(1 + MK/d). Finally, we choose
K/d, then have
K da log (1 MK a
d (d K ))
d M
MK
log 1
7
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 is
CPX = ((dd K/))MH)
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 dlosed-form solution of the regression problem w m.A (A m.
b m. where
A k m.A
Ek(h)) (osss,a')((
K(k))
+II
m = E1 (rn (s', a') + Vk (s")"s""))((ssdd
Note that E [KC())] is equivalent to (8, a, 8') E (k),(k), and the index set Um) consists of (k) and Utie, (I:). Therefore, the empirical covariance matrix A m,h and the vector by 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 statisties loc A A,, and loeg? to help solve the regression problem each agent.
m. to the server
For the local empirical covariance matrix loc A
loc
A l k
= E(e' aeelaateeee JEU a (8) a') d²)
this is the summation of up K d x d matrices. Note that [ a)ll S 1, thus it is easy see that the entries each matrix, namely, ('s,,'')((s' ('))'""" are bounded by Therefore, the entries in loz A m,, are bounded by K. For each entry in this matrix, it suffices to use Ollog K) bits to communicate between the server and the agent. Thus in each round, Odd log K) bits are needed to send the matrix loe A m.h"
For the local vector Ine m.
Ine b m E(t w0r (n) + V m,h+1 (s (ob(ss
this is d-dimensional vector. Note that Th is bounded by 1, Vk m is bounded by H and is linear with & by definition, which indicates only need communicate d-dimensional vector w wh.. obtain 1 m1++1 Similar to the above analysis, in each round, log ((H + 1))) bits are needed to send the vector kocb bh.h
Therefore, the total bits communication still only has a logarithmic dependency on the number of episodes K. This completes the proof.
D Proof of the Regret Bound for CO0PTS-LMC
The general framework for C-. and CoopTS-PPHE is closely similar. To make the article more concise, we first prove COOPTS-L.MC completely, which a bit more complicated. Then we can simplify the following similar proof for CoopTS PHE in Appendix G.
20

---

D.1 Supporting Lemmas
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- samlli- for N times. To simplify the notations, we eliminate the index before Lemma D.7 because the previous lemmas have nothing to do with multi-sampling.
Definition D.I (Model prediction error). For any (m, E MM [K] [f]] define the model error associated with the reward rhe
p (s, a) = (s a) + PA mi,++((ss) - (s,
Definition D.2 (Filtration). For any (m, k h) EMM [K] x [H], we define the filtration Fm, km as
(( (m.0mmmm))) U((sm. af... ae Proposition D.3. In Algorithm 3, the parameter wiihh satisfies the Gaussian distribution J.Ju Ik.Je) where mean vector and the covariance matrix are defined as (p m.h
Fmnkh = =((( an, (nTT))).MMM
k.Ju Pmhh
whi m.
+ Σ
W
w m.h:
1+1
A
Jun t1
(I AP (A (I+ A.) A44 ...
mih
Bmn
i=1
where A; I 27m A for i [k:].
Lemma D.4. For any (m,k,h) h) E M x [K] x [H]. the unperturbed estimated parameter w m.h satisfies
W S 2H Mkd/A.
Lemma D.5. Let in Algorithm 3. For any fixed O < < 1, with probability at least 5², for any (m,k,h) h) M x [K] [H] and for any (s,a) E A. we have
2d logooo10/
((s,a)
J. w mih
(ss, a)
m.k S
[ a) a)ll(at
38x
Lemma D.6. Let 1 in Algorithm For any fixed 0 < < 1, with probability least 8, for any (m, k. h) EM [K] x [H], we have
16 S HdVMK +
2K 8/2 del
Bs,
3
38x0
Lemma D.7. Let À = 1 in Algorithm 3. For any fixed 0 < < 1, with probability least 1 8, for all (m, k h) E M x [K] x [H], we have
Σ
((s',a') ('v
(1, - PA V P ( (s
< <3HVdCs
(A
where Css = log(( ( + 1) + log
2222K 25/2NM/
+ log 3 1/2
and Bş is defined in Lemma D.6.
Lemma D.S. Let À in Algorithm 3. Under Definition 4.1, for any fixed 0 < < 1, with probability least 1 - 6, for all (m, k, h)) E M x [K] x [H] and for any (s) S x A. we have
(bs a.) Witk mh Ta (s, a) P v m. (s, a) 5H 5H
Lemma D.9 (Error bound). Let in Algorithm 3. Under Definition 4.1, for any fixed 0 < < < 1, with probability at least 8 - 82, for any (m, k. h) E M [K] x [f]] and for any (s, S A. we have
d (s) < 5HVdc, + +
2d (VN/6)
+ 4
[1((s (At.)))>
33K
where Cs is defined in Lemma D.7.
21

---

Lemma D.10 (Optimism). Let À = in Algorithm 3 and co 1 2v
1 Under Definition 4.1,
for any fixed O < 8 < 1, with probability at least 1 - [C(E))co 28 where [C(=)] S (3/s)", , for all (m, k) E M x [H] x [K] and for all (8, a) E S x A, we have
fmm (s, a) I agE,
where as VMVKKM2222V BB/NMHK)
Remark D.11. Here we point out that in our proofs for both CoopTS-LLMC and CoopTS-PHEE, we use new E-covering technique to prove that the optimism lemma holds for all (s, E A instead of just the state-action pairs encountered by the algorithm, which is essential in applying this lemma to bound the term E 1 (5m,hs am,n) (5m.11 = k ml in (D.2) 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- normalizddddd term summation the multi-agent setting, which is first introduced by Lemma 9 in [24]. To make analysis complete, 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 run for any K> 0, M 1, and & the communication control factor. Define A = EmEm Ek= ( m,,n) (m n. + AI, then we have
(b ai tll. S (105 (de((A))) k=1
dct(A det(AI)
ΣΣ
det(AI) +1 M M
MK log
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:
(s) (f(s,)) Tm (+1s)) (Jm, = (-)))))))),,
Dm,K.h,1 = (Jm, (Qm, - (m) (mm,,) - (Qth n - Ommn (s
(sm, am.)):
(D.I)
Dm,K.h.2 (Pm, (Vi (V Vm 1) (s (mm, am,,n) (V (n,,b+1 V m, (sth (sm,)
Then we can decompose the regret into the following form:
k
Regret (K) = Σ
Σ
V
(sth.)
Vinli (sm..)
mEA k=1
K
Σ
(sm, :), Ex (s
Tm,nl- sm,)) nn - -m, (-1sm,))) (mm1 s
mEA k= h=1
Σ Σ
Dm,khh. Dm...
MEM k= h=l
(68)
K
(Eg- [ (Sm. am,.)smm.. = s - -16 - (Sm a)n.
MEA. 1= h=1
(152)
D.2 Regret Analysis
In this part, we give out the proof of Theorem 4.4, the regret bound for CoopTS-LMC.
22

---

Proof of Theorem 4.4.
Based on the result from Lemma D.13, we do the regret decomposition first
Regret ( (K) = Σ
Vm.1 (sm.))
Viniil (m
mEA k=1
K
Σ
Ex (s )) mmill (100m11m)))))))))))))mm)))))((
mm, (-88m, 18m,1 s
MEA k= h=1
(6)
K
Σ ΣE
(Dm km,k + Dm...n))
MEM Arm
(46)
ΣΣΣ
(Ex-
I (Sm by am,n))mm. s
1o (o am.))
MEM
(192)
(D.2)
Next, we will bound the above three terms respectively. Bounding Term (i) in (D.2): for the policy - have
K ΣΣΣN Ex. [(Q (6m, :)s mm 18mm)) The (m)mm, 18m, 5 S.
(D.3)
mEA
This is because by definition Tm.. is the greedy policy for Qm,
h +1 S H, based on (D.1), for any (m, k, h) E M. [K] x [H]. we have [Dm,k.h.1 S 2H and [ mm,k. I 2H. Note that km,k,h. is martingale difference sequence B[Dmn E[D Fm,k, By applying Dauma-Hoeffding inequality,
Bounding Term (ii) in (D.2): note that 0 S Qt
with probability at least 8/3, we have
ΣΣΣ
Dm.ta S K222M/3K
Note that Dm, is also martingale difference sequence. By applying Azuma Hoeffddn inequality, with probability at least 8/3, have
ΣΣΣ
Dm.k.h22 S K log(6/0)).
MEM k= k=1
By taking union bound, with probability at least 1 25/3, we have
ΣΣΣ D Dm,k.h.1
ΣΣΣ
Dm.k.h22 S 4/2MH"K
(D.4)
mEM
MEM
Bounding Term (iii) in (D.2): based on Lemmas D.9 and D.10, by taking union bound, with
probability least 1 - (C())lc) 28' MHK(8' + 822), we have
K Pf
Ex [ (8m,h) am, 11mm. = sth.1] The (sk (5 an,,))
mE.M 1=1
ΣΣΣ
Σ
(arge the to at.
2d (.llo(V///// VN/8)
4
HakE
ΣΣΣ
5HId0ss +5/
+
|| w-
3,xx
23

---

HMKKaa +
5HVdC& + +
2d 2dlog(VN/8) VN
4
Σ
( ama (a (=)
35K
hm
MEM Jimi
2d 2d VN/87
4
HMgage+ +
5HVdC& +
35K
H
(c
(ct(AA det(AI)
log
+1
M MV + 2
MK log
det(AI)
(Mlog(VN/88)
HMKa88+ + 5HvdC& +
38K
x (d((log(1 + MK/d) MMK//
+ 1)M + 2 MKdlog(( + MK/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 (|)(- S 1.
Here we choose dH /a///////a /as O \//HHSKKNN and choose
20H VdC
V3x
16
we have
Σ ΣΣΣ (En- I (Sm, MEA k=1k=1
smh.] 1 in om ((HH VdMK)),
(D.5)
occurs with probability at least 1 |C(E)lcb* -8' MHK(8' + +
We set 8' 8/12(MHK 1) and choose N C'ooo())/lool/////o where C == Ö(d), Ö()) then have
- [C(=)ld 28' MHK(8' + + 2 6/3.
Combining Terms (ii) together: Based (D.3), (D.4) and (D.5). By taking union bound, get that the final regret bound for CoopTS-LMC is OdHH² (dM / vdMK)) with probability at least 1 6.
E Proof of Supporting Lemmas in Appendix D
E.1 Proof of Proposition D.3
Recall from Algorithm 3, the LMC update rule is
Jej mih
Wm.h
A-j-1 Mm V L (w min
+ v 27m x Cm.
Agj
where we have V mih (hit--)) 2(A can calculate that
ki-1
bm.n): Plug in the above formula, then we mih
m.
k,Jt
k,Je-1
2mm. (Ak n w k. bb + v 2m B mm J.:e 2mm m h + / 22 Siik mn
Jude
w m.h
w mih
mih
(I 2mm, Ab m.hh w mih
k
(I 21,, A A wh N.
Σ 1=0
A. (2m,, + v 2mm 3 Bink Snah
kids kwda-1)
mih
Jx-1 (I 2m Bi
(I A "e w.o m.h
2mm
1=0
24

---

+
V 2mm m.k
2m Am, Cn,
1=0
where the third equality follows from iteration. Denote that A, = I 2m,m m.k Moreover, we choose the step size such that 0 < Am, < 1222mx (A (Am,k)) Thus we have
Ju
w A.Je
A
Ju A-1,Je-1 + 2mm.
A A w mih v 22mm. m.
A
m.
1=0
1=
J4
A
Jew
w 8- 1, (I (T+ As +.. 1)
w
+ v 21
Σ
A K.Je m.h
m.
1=
Jc-1
w m.h
W-w.-.Je k-1,Je-1 + (I 1 h + v 2mm B
A k.J2-1
m.k
1=0
Ag
mih
1,0
+
A+1
Jeh (I A W
k
J-1
A (.J-
2m m.
1=0
where the first equality holds because b A m.h W m.h and w m.h w m.h the third equality
1-1,JA-1
k,0
follows from the fact that I A + ... + An-1
A ) (I- A)-1, and the fourth equality holds
because of iteration.
Note that Emth d.J:-1 NO I), based on the property of multivariate Gaussian distribution, we have N bi.h, )) Then can directly get the mean vector
k.Jz mmh
w
k.Je m
A A
1.0 A/"
W m.h +
A
A11 (I W Wm,
Next we will calculate the covariance matrix I..
For simplicity, we define M,
V 22 g Ag
...AA Jo11 thus we have A11
M, J-11
Σ Alc A ~ v Σ MA -N(O,M, O.
J--1 Σ
A M.
1=0
1=0
Thus we get the covariance matrix Ikhc.
k
J.
sk.Ja m.h
M;
Σ
21
M
1=0
2m, m.
Ait
Jit1
Σ 1=0
A,
21m, 9 m.
3-1A
A
....Auu
Jus (I A?
A7) A ...
(I A? (A
- A,) AAAl J++ A..
[I
Bm,
where the third equality follows from the fact that I A A.... A 1-AA)([ A)-1 Here we complete the proof.
25

---

E.2
Proof of Lemma D.4
Proof.
Note that w
(Am,.))
6 " mn we can calculate that
W m.
(Amm))
b
(Am.)) -1
E
[ra(s',a') + vhh (s")
(6) Lol,at, (e1)EMa
1/2
/K(R)
Σ
||lra(',,a') + V Vrh 1 ( (amma)))
1/2
< 2H
VK(K)
Σ
0sss (b(s",a')lles ad)ll
S 2H (K(K)d/A
- 2H Mkd/X,
where the first inequality follows from Lemma J.3, the second inequality is due to 0 Vk I 1, 0 S Th < 1 and [ a)ll the third inequality follows from Lemma J.4, and the last inequality holds because (C) = (M - 1)k, + k - 1 S MR.
m. S
E.3 Proof of Lemma D.5
Proof. We separate the error into terms and bound them respectively,
(s) T
wh, (ss a) w m.h
(sssaa) (Ts.
( mih
Mm,h
a))s
(1 w
m.
(E.1)
Bounding Term I in (E.1): by
inequality, we have
((s,a)) a)TT (whtd m.h
&.Ji < (b((s.0)
kiJe w
m.h
By choosing k $ 1/(4)max (A 1) for all & and m. then we have
h I 20m, A mih & 21m Amin (A ())),,,,,
(E.2)
3 I + A - - A mnh & 2I.
Recall the definition of k.Jz mih
in Proposition D.3. By choosing Sm,i Bx for all E [k] and
m E M, then we have
((s.a)
k: m.k ((s,a)
(I p(8 a) T A A (I- (I --)--1-A -AA A.....
<
Σ
((s,a) A A A...
(Ai,)) -2 AA A duun ... )
((s.0)
383
2
Σ
a)) A A Jiti (Amm)) - (A -1) A Jinn A (s).a)
33K
i=1
$(s a) A ... (A (A) A ((s,a)
33k
26

---

33k Φ(s, (a (Am,))
where the first inequality follows from (E.2). By the definition of A m. and Woodbury formula, we have
-1 o ((()
(Amm)) -
-(Att) (A = (1 - A mih
E
(s E (k)
(((n = (A +
(A ( ' (A,
where so is matrix with the dimension of x n, is the number difference of (0s aa) between (Am,))= and (A)) (i.e. concatenate all @f (ss', d') into the matrix s)). Note that S M, then we have
Jil ((8,0) a) A A+1 (Amm,t) (A
A 141 .. (()
Ji11
Ji-1 (Anm.)) (I, 40 (Am,)) -1 ( "p' (m)'' -t) A A . ((s,0)
Φ(s,a)
i+l
Φ(s,a) a) T A J2
A,. Jim1
(Am,N) 06
p (Amm,h) -1 A ... ((s,a)
- Jon1
|| a) A
A..A/
J:+1 (A,,)) 1
A A.. (A
Ji+1
1/22/s/ss a) 1/2 (1(A, -1/2//1)
23z
II (1- 2mm umin j=i+1
(A (A tr (ep (Amm,)) ())))())ll(s.l. () ()
where ||-1| is Frobenius norm and the last inequality is due to - X A -'X) and (E.2). Thus we have
k. (b(( mm
2
II
(1- mm Amin (A (A 22, )ad tr (Aii,)))) (Amm.))+)))) (p))
33k
1=++1
( (ls,,a)liA+..... 1-1
333
Using the inequality
Va² + b2 aa a, > we get
2
II (1 (1-21gg 2mmm Am)n))) 5s tr(yp (Am.a) (1)) "
[ a) y
38x
j=it1
+ |1 a))l )llattiw))
def ck:
Nr ( ($(s, a)).
Note that have
1/2
NiJe
mih
mmmhh
(O Ia). By the Gaussian concentration property,
P
Je mith
-1/2
whith
k.Jz% - 1m,h
| /4dlog(1/8) < 82.
Then we have
((ss a)T T w mith
- (10,0) a)
k.Ju
2 s (0(s, a)) /
Mm,
P
(b(s a) T kiJe - ((s,a))
mm,h
k.Ju
> 2 dlog( (|0)) a) 1.ock
[
P
(b( a))
1m
kid
(xt))))-1 2 2 dlog(1 ( (.)
bRick
P
x J. mmh
-1/2 ///((w)) wide
w
N.Jec
22/dlog(1/0)
27

---

(E.3)
Bounding Term 17 in (E.1): Recall from Proposition D.3, we have
H Mm,h
Ju k A.....ivve
mnh
1,0
+
A
Jit1 i+
(I- A W
m.h
im
k
A
Ja A w 1,0
m2b
+
A
k
Jk
Jim1 (Wi,h w A "......AA wi m. W m,h .+1
Ag A (w!t.
m +
A ...A41
Jiti (Wim, -With + w m.
min
Then get
(( T w k)
a(s,a) A
(w"(wh min wi, +
+(s,
Σ 1=1
k
Ju
... A
1+1
Jost
( witth)
121
122
In Algorithm 3, we choose Wm,hh and Wm.hh k) b m.A O. Thus we have I21 0. To
bound term I22, use the inequalities in (E.2) and Lemma D.4, we have
1n2
Φ(s,a) a) T Ag.....A4 Jet (Winn witthe
k-1
II (1 2m Amin (A ( 13 11 ( a)] | II)
k
1=1 11j+1
k-1
Σ
II
(1
mm Amin J
2H (H
j=it1
Σ II (1 2mm.i Amin (Am))) J1 11b(s))))
4H V MKd
j=j=i
Thus we get
((s a) (u
k.Je
wk wh,n) S 4H 4H /Kd//
II
(1 2mm. Amin 2mi ) 116(s, a)ll
=1
(E.4)
Substituting (E.3) and (E.4) into (E.1), with probability at least 1 - 82, we have
((s.a) a)
A.Ja mih
Φ(s a)
w
1-1
(1-2 S (A 33 (1bb(s, a)ll /
2d log(11)
< AH / MKd/X
II
[1
alllaa
33x
j=i=
+
2d (olo((100)
II
(1 2m Amin (Am, J3 tr (sp (A - $ ||0(,, M
3,xx
def
(E.5)
Here we choose Mm. = 1/(4Amax (A ()) and set Nig = >max (A // Amiu (A then we have
(1 21m Ami (A (A (1 1/2n,)
28

---

We want to have (1 11-1// 1/2x,) < it suffices to choose J, such that
log(1/c)
J/ 2 log 1-1/2kg
Note that 1/2x, & 1/2, we have (lg(1/(1 1 1/2kg)) 2 1/2k, because e +>> 1 - x for 0 < x 1 Therefore, we only need to pick J, 2 2x, (1/E).
Also note that 1 2 || a)ll 2 V a))l((e.. and ur (T (A () S M due to the fact that n S M. By setting e = 1/(4HMKdl) Kd) and 1, we obtain
WE
4H (Kd/////l(((s.o)) +
2d (o/()
(10(5,
Σ
33x
2d 201og(1/8)
(10(,,,))llat
38x
2dlog(1/8)
|| (1)ss)))l
+ +2
(10((s,))llAtn
| (
33x
2d log(111/)) (1/8)
4
3)
[1 alll
38x
where the second inequality follows from [[ a))la, ( )-1 2 1/ 1/VK((k) + +1/0(s..)) a)ll 2
1 1/VMMK ((ss a)ll. the fourth incquality follows from Dk-1 chii-l E. é < 1/((1c) 4433. Finally we have
P ((06s.a) with (b(s a w w/nn
s (5)) 2dlog(1/8)
3 [
4)
+
33k
2 (((((s)))) T ()) we S sW)
min
This completes the proof.
E.4 Proof of Lemma D.6
Proof. Recall that w mihh N kiJu we have
- Let stich
w k.da
H Mm NNO0, Dmoch ), thus
k.da
Mm,h
J.Ja < mun + 11 Jell
(E.6)
Bounding (nch in (E.6): Based on Proposition D.3, we have
p
K.Jx
=
A
A J w
1. A
m.h
+
(I A Winn
k
A
A
2H MKd/X
A
AI A/
<2Hd
|
J
(I-
29

---

Je
2 SHHd/M//A
II (1 mm Amin (A mm,)) ([] + ||Aillg))
2Hd MKHd MK/A
II (1- 2m min (A m)) (1+ (1 2 A)) j=
where the second inequality holds from Lemma D.4, the third inequality follows from the fact that rank (A max (X).
A Jesl
141 (I A.))) s d and |X l2 I X|| S rank(X)||X[|2 where ||
Recall that in Lemma D.5, we set Jj 2 2kg log(1/c) where Kjj Amax (m,,)) Aminn (A I.
c= 1/(4HMKd) and 1. thus we get
1 S 2Hd MK/A
h- 1
I MK/A
16
$ 3 HdVMK.
Bounding | in (E.6): Note that ch.Ju N(O. E =m:h). using Gaussian concentration Lemma J.5, we have
P || S V 5 tr (Imilt) 2 1 1
Recall from Proposition D.3, we have
h 1 tr (A Je
tr (x
A Jen (I (I
(A A.) AA AAL ...+At)
x=1 3m,i
k
1 tr (A
.r (A (A ...t)...r
...tr
tr (I - A? tr ((Amm))) tr ((I A.)
1=1 Bmnk
x tr 1:11) ......rrrr tr ")
where the inequality holds due to Lemma J.6. Recall from (E.2) that, when Bm. S 1/(4)max (A ()) for all & and m, we have A. * (1 Amin (A )),, ))
Amin
set X 1, then we obtain
tr (A)) S tr (1 2m Amin (t) 1 s d(1 Amin (At J S de < 1. Similarly, we have I A??
23, < (1
1 II then we get
2.0;
tr(1 A 22 S 1
d < d.
22%,
Also, based on (I+ A1) 21, we have
2 tr ((I+ < d.
3
Note that Amax (AAm.)) < 1, we have
S E(((A < d.
Combine the above results together and choose 3m,s = 3x for all E [K] and m E M, we have
K
tr
JinkiJ mihh
1
2
8
2
K d
Bm,i
3
333
30

---

Then we have
P S
-
1
2
Kd
P
|| - tr (Imih)
21-6. 8.
V
33x
Combine above results together: with probability at least 1 - ò, we have
|| wh/h
16 HdvMK +
2K d3/2.
33xd
This completes the proof.
E.5 Proof of Lemma D.7
Proof. Based on Lemma D.6, for any fixed n E [M], with probability at least - 6, for any (m,k, h) E M [K] [H], have
16
2K
k.Ja.n W m.h
S Hdv + V
d3/2.
3
33xd
By taking union over n, m, k ht we have for all (m, k, h) E MM [K] x [H] and for all n e [N], with probability 1 - 8/2, we have
ANMHK2
w
J.Je m.h
"I
HAVMK + 3
8/2 B5/2NMHK-
(E.7)
33x
Based on Lemma J.7 and Lemma J.9, we have that for any and d 0, with probability least 1 - 6/2,
Σ
105', ((Vm,htt PA PAVA
(st, (
(sf,al, .s (s" mu (8)
(AR mi
ho +
B5/2NMHK
3
8
1/2
<
2
log
+ dloog
+ log
+
8
d log
k +
Ba/2N
1/2
2 2/2KE
< 2H
+ dl d
log
VX
Here we set
1,E
with probability at least 1 - 8/2, we have
2V2k"
((5',a") ((VV) m,,+ - PA ( (s',
as',at,s" ( (m)))
(A# (A,,,) )-
B5/2NMHK
3 3/2
1/2
s 2/1 2H
log(k: (k= + 1) + log
+ log
+ H
H
2/2k
(2/2K B5/2NMHK
3 1/2
37//2
s 3
log(K K + 1) + log
+ log
(E.8)
2
H
5
By applying union bound between (E.7) and (E.8), and define that Css
1 log K + 1) + log 3
2/2K Ba B./aNNnK)
))
1/2
log
finally we obtain that for all (m, k, h) E EMX [K] [H]
Σ
( a [(V.. PA V. ( (s',
< <3HvdC's
(sl,at.s ())
(A
with probability at least - 8.
31

---

E.6 Proof of Lemma D.8
Proof. We denote the inner product over S by (s)ss. Based on Px((Is,a) ( (.)) in Definition 4.1, we have
Ps Vontt1 (s, a) Φ(s,a) (wn, 1
a) (Ami,)) - (A (pen Vin
o(s,a) (Ammit)
E
o(s ((()a))((s'dd) d' + +Al (een, v vmatids
Φ(s,a) (Asm.))(AAmm)))
Σ
('s (IF (t) (5', aa)+ Mlpp Vm
(matids)
(ad,al,
(E.9)
Here the last equality uses Ph (-)(()),)) = ( un))) ())) again. Then we can separate the following error into three parts,
Φ(s, a) Wm.n (r)(s,a) - Ps PAV (s
=s(s (Am,,) (An,.))
E
[ra(s',a') + (s") - (s,
(at (Em
- as) (AAtm))))
Σ
0(5' a²) (Px Vh (s' + Al V Vmattls)
(staal,"")
((s, a) (Aii,t))
0(s' ass [(V m,++1
PA PAV Ph (s) (st,
(ot at o0 Em
+ (8, a) (A
rh ( ((( - ((,
(sl (t)
- -Ap(s, (A (pns
(uns V Vi.
(E.
(ii)
Here the first equality holds due to (E.9). We now provide upper bound for each of the terms in (E.10).
Bounding Term (i) in (E.10): using
inequality and Lemma D.7, with probability at least 1 5, for all (m, k. h)) E M x [K] x [H] and for any (s, a) E E x A, we have
((s,a) ((s,a)((Amm)))
(A
((st,d'((VV,) m.,+1 VR ( [s,,)a))
((s', [[)[
[(V
PA V v1) (st
m,,+1
(e",at,e"))EUm.a
(A+ (A
$ 33H ())
(E.11)
Bounding Term (ii) in (E.10): we first note that
a(s,a)T (Atu))
ra(ct,a))0('''a)) (s)
= ((8,a) (Amm))
ra(s' r((s)_)))((ssdd)) () Tr
32

---

a(8,a) (Amm))
Σ
- Amunrr)
<(s,a) (Amia) (Ami))(Amm))))))
Σ
E
On 1I
(ot,at (ateu
=(s,a) (Amir)
Σ
E
p( a's'aa))r 10h
(""
=->0(s,a) a) (Abu))) On:
(E.12)
where the first and fourth equality holds due to the definition rn(s,a) (o(s, 0n) from Defini-
tion 4.1, the third equality uses the definition of A m. Next we can obtain that
-) h) 0r S Allo(s, (0 (laa, 1001l
s V 110
s \ (m
(E.13)
where we use the fact that Amax ((Am..) Combining (2. and (E.13), we obtain
s 1/2 and |0 S vd from Definition 4.1. By
((s,a) (Am,))
ra m(ddd))(s(,d)) -ra(s,a)= s VAd]lo(s,a)llas -
(dt,at a (1)
(E.14)
Bounding Term (iii) in (E.10): we have { a) ( m.) (pn, V M S a)l Kl V v)
Vāllp(s, 1- Vrk Vhh sll
H a)) 11
H Hv slsss,))l)) a) ( -1
(E.15)
where the second inequality holds due to the fact that Amax ((A "1 S 1/A, the third inequality uses the fact that Vk M,,+1 S H and the last inequality follows from || || vdd in Definition 4.1. Combine Terms (iii) together: combine (E.11), (E.14) and (E.15), then set = 1, with
probability least 1 ō, we get
(sssa) Tw m. r, a) PAVE - ( < (3ICs3 + Vtd H HVAd l a))
S <
This completes the proof.
E.7 Proof of Lemma D.9
Proof. Recall from Definition D.I.
1b mn (8, a) = (8, rn(s,a) - PP PA P
(8.a) (8,
m.h+
min { max ((s,a) TTT k.J. w
H h+11 11+ - (8) -P -P (
[E(M]
mi
< max (bs, a) <c[N]
ww A.Jain (8, - PPak (h.
Wm.h
= max Φ(s, a) w m.h =E[N]
w wm.n. a)) -IP vk (hh,) Φ63, a) T "hh + Φ(s,
33

---

s max ( a) "iih NENN
w h + +[s(s,)
W
rr((s,a) PAV m1)))
12
Bounding Term I based on Lemma D.5, for any fixed n E [N], for any (m, h, M and for any (s, a) E S x A, with probability at least - 8², have
4 2d ldgog(1
[o(s, a)"
Wm.h"
J.Je. a(s,a) whlls S 5// m.
| a))(())) a))(a)))) 3
33x
By taking union bound over n, we have for all n E [M], with probability 8², we have
2d (vN/6)
( a)) w k.Je. mih
((s, a) wit wm,l BV
(ss a)ll(a
33x
This indicates, for any (mn, h E MX [H] 1 - 8², we have
[K] and (s, E A. with probability least
2d (VN/8)
4
Term 41 max [0(s, a) NE(N
w K.Ju. mih
a) wh m.hl (5V
+
| )100 (l)la
38K
(E.16)
Bounding Term Iz: based on Lemma D.8, with probability at least 1 - 8, for any (m, h k)
M x [ x [K] and (s, E S x A, we have
(b(s, a)
we m.h x a) V m. (s, a) s 5F/
Combine the two result above, by taking union bound, with probability at least - 8 - 82, for any hm, E M [H] [K] and (s, A, we have
2d log (VN/8)
4
-th mm a) & 5HVaCs + 5/
+3 [
33K
This completes the proof.
E.8 Proof of Lemma D.10
Proof. Recall from Definition D.I.
(s, (s) + PA Vi Ph (s,
(s,n(s
Note that
H - h 111 S max Φ(I, a) w k.Jen k.J. max Φ6s, a) w m.h RE(N]
(s, = min
m.h
nE(N]
Note that [| (d(ssa)ll(ss
///A|/b(s, a)ll s for all (8s, a). Define C(s) to be e-cover of {Ø || - S 11}. Based on Lemma J.8, have IC(=)) (3/=)d.
First, for any fixed (bs, a) C(s), based on the results in Proposition D.3, we have that (ss,a)
T k.Jui mih ((((s,))) a)T "mii Tubil pfs a) shi ((s,)) for any fixed n [N]. Now
define
Z a)( + PA Vk ( (ss, a)
R.Ja
((s
k.Je (bs a) m.h
When Zul < 1, by Gaussian concentration Lemma J.10, we have
P (6s a) Tw k.Ja.
2 (s) a) + P. Vk (1 (s))))
m.h
34

---

Φ(3,a) a) T k.nk.n
W
mnh
(65,00 a)
k:Ju rn(s, + Ph V mi,+i(8, ((5,a) a) mm,h
V a)) I Emih ((5,a)
(o(s,a) TE tm (()
Φ(8,a) a) w k.lk.n Φ(5,00 a) Hmihh
P
mih
2 Zs
v V
Lk.J. ((8,a) a) m.h
1 exp( (
2/
2/2ex
Consider the numerator of Zg:
(n(88 a) + PA mit (8, a) (0ss a) Mm,h
k.Jy
< <|nx(s,a) + Fn V (8, a) - ((8, a) w Wm,al + ((( T Wh., - ((ssa)) a) Mm,h
Based on Lemma D.8, with probablity at least 1 - 6, we have
(ra(s,a) a) + P. m.++ m (8) a( wh wh. S5HVicallsss (a)l(tt
From (E.4), we have
II (1 2m Amin (Ami.n 4o 11 a)ll-
Φ(s,a) (mmmh
Wh,n) < 4H MKd//
2x, log(1/e), then we have for all j [K]. (1 2mm Amin (A m, 1) S E, e 1/1111/HHMKK and X = 1, we have
Recall the proof of Lemma D.5, set 7m..j 1/(4/maxxAx (A ,),
(6),0) T m.,h - Φ(s, a)
T k.Ja
mn, S AHVMKd
1|((s,
4H AHVMKAL MKdv MK k
4MHKd
Øss a) alll
So. with probablity at least 8, we have
(SHvaC.+ + 16(s..))la ( --T. (E.
())(s,a) + PA Vk (1,,41 - ()s,a)
k.Je m.
<
Consider the denominator of Ze: recall from the definition of m.h from Proposition D.3, then we have
(b,,a) a) Ek. ((s,a))
Bm, (( A
J4i (I- (A - (I+ A .......A" ...AA (s)
A,1
(6s
a) A
A (I 22
A Jit
A ((t,)a))
1=1 2m3.
where we used the fact that I x (I+ A+)-
Then we have
a),,a) E (s) a)
2mmm ((s.a) A/t
J4t ((Aim)) A!' (A...)) -'AA'AA ... AL
1=11
35

---

((s,a) a) T A A ((Ama))+ ((A -1) A)A 4T ... A
20x
2 o(*, A (Amrhh) - Ar A a(s.a)
Φ(8, (A (()())))
2
By the definition of A A, and Woodbury formula, we have
(Att)) (Ammh)
A Ammn
E
(ot,al (et)), (1))
(1)
+ + (A
(A
=
where to is matrix with the dimension of d x n, is the number difference of ((s', , a') between (Am..) - and (A (i.e. we concatenate all (5s a') in to the matrix sp). Note that n s M,
we have
Φ(s, a) A A J+t1
(A A 4 ...AA (ss,a)
((s,a) a)
Jn
A
J/-1 (A
(In, + + (A " "T
A ...AA ((s.a)
k
i+1
S Φ(s,a) a)
A Jv J:-1
++1 (Ain,)) -1 1p6 (Amm.) -1 A
141 ...AA Φ(s,a)
Jet1
= =I|0(,,0 a) T A ...AA: i+1
1++1
1 (A -1 *pl12
S || ....A ...AA:i (A
J.+1
( > 1/2 (8,, a))
-I((A 1/2 1/22
2
II (1- (1-2 2m Amin (A (A) j=i+1
ir (1p (A (
(l( a) (l
where || is Frobenius norm and the last inequality is due to ||A ||- x tr xr(XXA-Xx and (E.2). Therefore, we have
((s,a) a)
Emich (88,a)
k (1 Amin (A |
> 1 (b(s,a)l?
II
2,x (At a,
2,Kx
i=1
1 II (1 2mg Amin ()
203 tr (4p
(1 al)) 1-
23K
-=1-1
Similar to the proof of Lemma D.5, note that tr (4p (A (pp) I M, when we choose J 2 2k, 1o)(3kM), we have
||0(1, al
2
1
[ (1((,)))(a
a))s
VM
|1 (a))
2/3x
(3KM)*
(3kM)*
1
[ 1
|| ((b((8,)))
a)ll
1
2 2/Bx
3VkM
6vKM
1
| a) a)l(aa ((t)))))
(E.18)
AVBK
where we used the fact that Amin ((A m,,h )1-) 2 1/kM and (1)((s ,. 2 1/VKM 1/VKM|l0ss.n (s((s,)))) Therefore, according to (E. and (E. with probablity at least 5, holds that
(x(8, a) + PA Vhh,+ x+ (8. a) $(s,a) a) mmih
k.Je
22
Vos a) Liick (8,,a)
36

---

5H v dC's +
4/7K
which implies [zx| < 1 when
V /DH +
Till now we have proved that for any fixed Φ(s,, a) E C(e) and for all (m,h,k) E M x [H] x [K], for any fixed
[N], with probablity least 1 5, we have
P ((
a)
w k.Je, (s,ss, a) Ph V m (s, 20) (0) m.h
2v2cx
By taking union bound over E [N], with probablity at least 1 - 8, we have
1 N
P max {db(s, [N[N]
W m.h
K.Je.n
(s a) Pr V mi (8, 2 2 21-2et =
6
2V/2eT
where c6 =
Therefore, for any fixed (ss, a) E (e) and for all (ra, 1t, k) [M
2v2e0
with probability at least (1 - 1-5))11 (6") > 1 - 8 co" we have
max nE[N]
{ a) T w Ju (s, a) Vi m,++ (s, 2 0. m.h
(E.19)
Next for any Φ = ((s, a). we can find Φ' E C(s) such that 1 lob-d'llan &'Il(at, (A S.. We define
AΦ Φ Φ¹. Recall from Definition 4.1, we have
(8 + Pn Vik m.++1 (8, = Φ18 a) Or + ((s. a) (no, V 1))s ((8 a) Tw m.h
where w m.h = On + (mi, VA sh Note that max{|lun 110, S vd and Vk H- h S H. thus we have
m,h+1 S
| S 1100 KMn V ii S Sva+ 2HVO.
Then we define the regression error Awt m.h = wht
-
m.Jeim Thus we have m,k
m.n
max {s a) N
w
R.JE.n - (n( - IA -PAVVM (PN max { - Φ(s,a) Aw A. m.h
RE
Then by Cauchy-Schward inequality, we have
Φ Aw
Φ6' Aw m. + AΦ Aw wh.
2 Φ² Aw m.h ||b11 Aw m
Φ6 Aw m.h VMKe
A & mll
By triangle inequality, with probability least 1 A| & lI S //w + (w k.J." S 2H + BBJNMHK
5, we have
Denote 0gg VMK (2H VMK(2VV + B5/NMHK). Then, for all (m,h,k) E M x [M] [K]. with probability at least 1 6, we have
{Φ Aw nE(N
max
max [E[N]
(Ø' Aw m.h - aage.
Recall from (E.19), by taking union bound, with probability at least 1 - [C(e))cb* 25, for all (m, k) E M x [H] x [K] and for all (s,a) E S x A, we have
max NE
{ Aw 2 06g5.
Finally, with probability at least (C()) N 25, for all (m, h, k)) M x [H] [K] and for all (s, a) E S x A, we have
1 1 (s, a) S age.
This completes the proof.
37

---

E.9 Proof of Lemma D.12
Proof. For simplicity, we denote (s n) n)) as 2 Then we consider the following mappings (UM, [MK] - [M] [K],
VMr (T) (mod.M) PK
M
where set Pn (T) M if M|T. Next, for any 0, we define
TM
A AI Σ
( (u(( (ar(
Φ
(ex(() Uar (w)..) ( for O,
A = AI, =
We denote = , ) the synchronization episodes, where [K], also denote do = O. Then we separate the episodes = I,..., into two groups based on the following condition,
det(A,) S 3.
1
(E.20)
det (0, (1-1)
Note that the left inequality always holds due A, z Ag and the trivial fact that A B det (A) < (B). Then we define that 11 {k E N+ k E (0,-1,0,), Vi E (E.20)))) is true) and 1 = (k E N+, k [o,-1. Vi E [n] (E.20) false). then [K] = 1 U 12 U {K]. For any E (;) and & E I,, note that - A m.h & A & Ag. thus for any m E M, we have
det(AA)
(=m, (aa S || (
det(A
det(A
s 2 (=m
(E.21)
where the first inequality follows from Lemma J.12, the second inequality follows from the trivial fact that A & B = (e)(A) & (B), and the final inequality holds because k E T1. Then we will bound the summation for l E I1 and E 12 respectively.
Σ kEZU MEM
Σ
MK Σ
Σ
( M. (
mEM (E]U(()
2
MK
Σ
Σ
mEM KEMEEEUEK
22 MK Σ Σ
( 11 11(
MEM
(ct((A))) det(AI)
$ /2
MKlog
where the first inequality follows from Cauchy-Schward inequality, the second inequal- ity holds due to (E.21), the final equality follows from Lemma J.1 and A Σmem Ek ( an (0(( (s o....) + AI.
For any interval (0;-1,0;), define A; Gj 0;-1 - 1, we calculate that
1
Σ ( (Ak a S
A
Σ
[
(
1=0.-1
38

---

det (e
A log
(Ae(A
where the last inequality follows from the synchronization condition (3.3).
Define Rg
log
det((A dee(AA))
note that nn K, then find that
(Ae)(A, Σ
(et(AAg)
R₂
log
log
det (et
(
t=1
We can claim that Iz has at most RA synchronization episodes, otherwise
(e de 1.-1)
(et(AA)) de 1
R
log
Σ log
> R4 log 3,
iefilo--nEla)
which causes the contradiction. Thus 1z has at most Rd intervals, then we get
E Σ
( S R.M.ES ( [oog
[dct(A deet(AT))
+1) MV. )
RET MEM
Finally, we can bound the total summation,
Σ mEM
E
Σ
| & aommillllll..... +
Σ E
(
mEM KETZ
mEM (E)
del(A dot(AI)
+1 )
det(AA) det(AI)
log
MK
This completes the proof.
F Proof of the Regret Bound for CooPTS-LMCC in Misspecified Setting
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 what have presented in Appendix D and Appendix E. Here we mainly point out the differences of proof between these two settings.
F.1 Supporting Lemmas
Definition F.1 (Model prediction error). For any (m, k)) E M [K] x [H]. we define the model error associated with the reward Fm,hs
t (s) Tm.A (s, a) + - Pm,hh V
m.b+1 1 Qth as,
Lemma F.2. Let À = in Algorithm 3. Under Definition 4.8, for any fixed 0 < 8 < 1, with probability least 1 5, for all (m, k, h) M x [K] [H] and for any (s. E S x A. we have
(bs a) Tw mmn (m, a) TP min V (8,
< (5HVdC, + 3H(VMKd) | a)lA + 3HC.
where Cs is defined in Lemma D.7.
Proof of Lemma F22 Recall from Definition 4.8, we have
Pm Vk
m.++1 (8, a) - $6s, a)T
( (ni, V w sl S |m (- a) ()(s,)), ().mm)))))lll)))))) 1h
< 2H P m. s, - (d(s,,), un)
39

---

2HC,
where the first inequality follows from Cauchy-Schwand inequality, the second inequality follows from the fact that II m,t+1l I H and P2, P| Pallrv = Σxew Pi(x) P2(x)] 2
Palli for two distributions Pi and P2, note that here we regard distribution as infinite dimensional
vector, the third inequality follows from Definition 4.8. Define Am,1 = Pm, V m, (s.
((s,a) (mh, Vk m) thus Amm S 2HC, Then have Vhh
P Fm, Vi (s,a)
(F.1)
Φ(s,a) (mn, Vol. mi)) + Am,1
= a(s,a) (A
E
((d,d))((ssd)) 21 (nr, V Vmnttads + Am,1
XI
(stiat (l)))mm
= =((,a) a) (A
E
* ((() (pnns (pnn (matt)s)
( (E)))
+ (A
(Ne Vi m + Am.1
=(s, (A
((s',a') (Pm. (Pma
(ot (m)))m,,)()))
- (bs a) (A (Am,)))
E
(m,
(o) x
* Ta (A (, ( (pns Vk ( + Am,1-
(F22
Based on (F.1), separate the following error into four parts,
(s,,a) T W... am) - Pm Pl (8.
= ((Am,) (Amm,)
Σ
(mmn(s',aa) + V ( ( (8,
(st (E)m.())
- -((s ((s,,)((AAE,)) (A
Σ
8(s' (P (i Vik nit (s¹, (s',
(ot (alla
+ ((,,,) ((A (Am.))
o(st,a))
- -) (A T( (Amm.))
(pens Vol (nhbti)s - -m.1
Σ
-Pmm $65 ('s,a') [( m,++1 Pm. Vi (s)
JEU
m.
+ ((s, (Att))
Σ
Imm (s', ('' - (8.
(of aaiiallo .or! (e (k)
A( (pen, vob voi.ntt)s
(i))
+ Am, (AA (Atha))1
Σ
o(st,a") Am.
(F3)
(al a
40

---

We now provide an upper bound for each of the terms in (F.3).
Bounding Term (i) in (F.3): same as (F,11) in Appendix E.6, with probability least 6, we have
Term (i) s 3/l Vdd a) )-1
(F.4)
Bounding Term (ii) + Term (iv) in (F3); define Am, = Tmin(s, Φ(s,a) T On. then we have Amm Ç due to Definition 4.8. Next have
Φ(8, a) (T
Σ
( Tm)((o,a))
(ot at ("")Ul""
=<(s,a) (A
Σ
(m ()( T0 0r.- -mm.2
(ol.at, (ol,at,s")) (l))Em
= ab),,)) (Am..))
Σ
(mais',aa' Amannn Am.2
(ol.at,o" (
= as) (Ami))
Σ
Σ
(''sa')o(s'' " On. A101 -m.
(6t "a (.5
= a();a) (0As;))TAAmm)))))
Σ
((s A'm -2I0% - -mm,2
= ->
((( (Atto))-- On + Amp (Ato
Σ
o(s),0))
Am,, (E.5)
(ot ja JJ (8)
where the third equality uses the definition of A m By Combining (F.5) and (F. Appendix E.6, we obtain
Term (ii) + Term (iv) S (s)ll + Term (iv) + Term (v)).
(F.6)
Then we calculate that
Term (iv) + Term (v)
= (Am,1 + a)
Σ
o(sh.d)) (Am,1 + Am2)
< 1m + Am.el ((8, (As,,))(Amn.)
E
$(8' .0)) + +1Am,1 + Am.l
< <3HC(16(5,0)
Σ
||0(0", aa)aa)))
) + 3HC
(a (K))
< (3H(lo(s..))l(Ne
(C(1c)
Σ
| (10ss"at)]leae
+ +3Hz
<3HCVM a))l +3H,,
(F.7)
where the second inequality follows from Cauchy-Schwar inequality and the fact that Am, Am.2l < |mm.1 + |l < 2HC + Ç 3/f the third inequality holds because of Cauchy- Schwarz inequality, and the last inequality holds because K(k)= S MK and Lemma J.4. Substitute (F.7) into (F66,, we have
Term (ii) + Term (iv) S (3HCVMKd + ())) 3HC.
(F8)
41

---

Bounding Term (iii) in (F.3): same as (E.15) in Appendix E.6, we have
Term (iii) I H HVAd| a)lla) --
(F.9)
Combine all the terms in (F.3) together: by using triangle incquality in (F.3,, we combine (F:4), (F8) and (F99, then set À = with probability at least
get
Φ(s,a) a) w m.h (s, Fn Vk m. (8,
3HVdCs Vd HVV Mo..d+HHCMKK [ alla,,) 3H1
+ + (((e.)))) +3H,.
This completes the proof.
Lemma F.3 (Error bound). Let À = 1 in Algorithm 3. Under Definition 4.8, for any fixed < d with probability least 8 8², for any (m, k, h) M [K] x [4] and for any (s,a) 8 A. we have
- ()) S 5HVaCs +3H +5 5V
2d (VN/0)
+ 4
1l(s) +3HC,
33K
where C3 defined in Lemma D.7.
Proof of Lemma F.3. We do the same process that in Appendix E.7, and we have
1/ mm (s, a) & max
(o(s, a) w k.Ja. - Φ(5 w Tw m.h
m.h
NN[N]
lbss a)
w m.
(s, I mi V mi,4i
(18)
Bounding Term (i): based on (E.16), for any (m, h, k) M x H x [K] and (s, E S x A, with
probability least 1- 8², we have
2d log (VN/5)
max (8) aTTT w k.Je. RE[N]
(b8 a) we mm.ll s 5//
+ | a
m.h
33x
Bounding Term (ii): based on Lemma F.2, for all (m, h, E MX H x K and (s,a) E E S A. we have
+HH.. Combine the two result above, by taking union bound, with probability least 1 --2 82, we have
(Ø(s,a) a) " - (s, - Pa Vo (s, s (5HvāCs + 33C MKd (
2d log (VN/6)
4 | allaas 3HC.
-1 (s, <
SHVaC's + 3HCHHHCMAA +
+
38x
This completes the proof.
2/2en Under Definition 4.8, for any fixed 0 < < 1, with probability at least - -C(()) N 26 where |C(s) S (3/e)d, for all (m, h), E M [H] [K] and for all (8, a) E A. we have
Lemma F.4 (Optimism). Let in Algorithm and c6 1 1_
(s, S agE + 3HC,
where as VMK(2H2 BBS/MHK).
42

---

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(E). Recall from Definition F.I.
t u a) = (m, a) + P Pm,h Vkk m, im, (m,
Note that
Qm = min
max ((3, a)" w kidein nE(N
. - h +
max Φ( a) w M.Je.n m.h
m.h
ne(N]
Here define
Vm Tm. (8, + m. Vk m,h+1 (s, +[(s, a) Mon (Am,1 + Am,2)
Zk
V)(s,a) ( S ((5,0)
where Am,1 Pm, Vh m. (s, - a( (Hh, Vol s Am = (m,
((s,a) T Based on the results in Proposition D.3, we have that Φ(s, a) T k.....n
mi,h
N( ((s,aa)))))))))) a)" with Φ(s,a) a) Emih (m,h0(s,a)) ((),a))) for any fixed [N]. When |Z 1. by Gaussian concentration Lemma J.10, we have
(m..(ss,)) + Pm. Vi Vm, - Φ(s a) T A.Jk.n S (Am,1 + Am.2)
(()(s,)) T k.Jain (m) Pmin Vnl (8, - (Am,2 Am.2))
mm,
((, Twoe]w""ee
w k.Jp. a)) wiih (mi(ss, P. V m, (8, (Am,1 Am.2) - (68, a)) Me
mih
Vo((s,a) (ols,a)Tt,n 1'thh (s).a)
v (b((,,)) a) st.
T (ss.a)
P ((,,a) w
k.Je a(),a) 1mih 2 2n
mih
V Vo((s, a) ( Sttch (ss
exp( exp(-2?7 -Z?//2
2/2
2/eeT
Consider the numerator of Zy:
(m, (8, a) + P Pm,, Vk mm (8, a) - (bs,a))
pmih (Am, + Am,))
k.J.
< (m, a) Pm,, V m41 (8,a) a) (w wh Wi.h (Am,1 + Am22)
(bs a) wh Wh, Φ(s, a)T p K.JJ
(F.10)
Bounding Term I in (F.10): recall the proof of Lemma F.2, we do the almost same error decompo- sition as (F.3) with the only difference of adding term (Am,1 + Am,2)
((8,a) a) W/. -mm,h (8, a) - Pm., V. mi (s, + (Am.1 + Am,2)
= a(s (Am.N)-
Σ
a(s' ('v(b,
m-h- Pm V ( (s) ad))]
(es,al,s"))ed ((k)
( (''''')((ss' .d)) (s
+ (As
Σ
(sl (st
-Ap(s,a) ( -2 (mn vi vinnttas
43

---

+ *Am10(ssa)) a) (Am.))) (A
E
o(5),0g)
m
(F.11)
(ot.al, "eaa,,"))Emmlll
(iv)
We now provide upper bound for each of the terms in (F.11).
Bounding Term (i) in (F.1I); almost same as (E.11) in Appendix E.6 with the only difference between P4 and Pm, with probability at least - 6, we have
Term (i) S 3HHilcll (
(F.
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), have
Term (ii) Φ6 a) (Amm.))
E
Tm, (s'saa)))((sss am)(s,,))
(e) ool.oola' Je
->x0(s,a) (Amma) Orn + Am. (Am,)
E
0(05,09)
A..
(F.13)
By Combining (F.13) and (F.13) in Appendix E.6, we obtain
Term (ii) Term (iv) s vAd [d. -
Term (iv) + Term (v)).
(F.14)
Then we calculate that
Term (iv) + Term (v)) = |mm, + Ampl (((s,))(AAmn)))
Σ
o((',a")
(et,at
E
|| a d')l(a
(st,at ast,atis (UU
1
K(())
Σ
( (m
(ol,at aEU,
S 33HV (()
(F.15)
where the first inequality follows from Cauchy-Schvve -Shwarr inequality and the fact that Am, Am.2 S 3HC, the second inequality holds because of Cauchy-Schwar inequality, and the last inequality holds because KCk)= < MK and Lemma J.4. Substitute (F.15) into (F.14), we have
Term (ii) + Term (iv) s (3HÇVMKd + v Ad [| a) (Att
(F.16)
Bounding Term (iii) in (F.11): same as (E.15) in Appendix E.6, we have
Term (iii) < H VVV/ll((ss a) a)ll (A
(F.17)
Combine all the terms in (F.11) together: by using triangle inequality in (F.11), we combine (F.12), (F.16) and (R.1), then set À with probability least 1 5, get
Φ(s. a) T wht (m, a) Pm vik
Mm t + (Am.1 Am,))
$ (5H + 3-HHH MKd) [[ a) l)
Bounding Term 12 in (F.10): same the proof Appendix E.8, we have
4
((ss T ((s,a) Mm,h <
3 [o(ssa))l(a,,
44

---

So, with probability at least - 6, we have
(5HvaCa+ + +3HC + o 100
(m) a) + Pm,h V de (s,a) b(s,a) miih &
(F.18)
Consider the denominator of Zu same as the proof in Appendix E.8, with (E.18), we have
1
(0(s, a) stit 2
( )-
(F.19)
4/BK
where we used the fact that Amin (( (m)))))))))))) 2 1/k and (1 (p(s,))l(ne a)llas w 2 1/V Therefore, according (F.18) and (F.19), with probability least 1 6, it holds that
Tm, (s, a) + P. m. Vk m, (s, (ss,, a)
mm
J.Ja
7
VØ(s, a) Enh ((s,
(5HVCCs + 3HC MKd + [10(,,))l(at...) - 1/8x
(5s a) a)l((a).
5H + 33HHHMKK +
4v/K
which implies |2x] < 1 when
2011 Vacs 12H(CMKK 16
V
Now we have already proved that, for any fixed n E [N]. with probability at least ô, we have
P ((mmA(B,a) a) + Pona Vh 1 a) Φ(8 a)
T J.J.e. m.h
S (Am,1 + Am.2) 2 1
2eT
By taking union bound over n E [N], with probablity at least 1 - 6, we have
max N
{ a)
J.Jein w m.h
(8, a) - Pm, Vb m m (8, 2 -(Am,1 + Am,2)
N
21
2em
=1 =1- cN N
where cp =
Finally, with probability at least (1 - 0) c,,,,, for all (s,a) e
2v
have
the (s, a) $ 3HC.
Till now we have completed the proof of fixed & E C(e). Follow the proof in Appendix E.8, we can get the final result.
F.2 Regret Analysis
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 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 (iil) in (D.2); based on Lemma F.3 and Lemma F.4, by taking union bound, with probability least 1 (C 25' MH 812), we have
Σ
(Ix,. 1 (Sm,hs am,h (m 18mm1 s ( (s a)h
45

---

K H
1h (o I) + crgrE + 32C)
meM k= h=1
K H Σ
2d log (VN/8)
4
5HvaCs + +3H(VMKd+ +
[1 a amaalleat
3,K
3
mEM k=1
+ 0gg + GHÇ
2d (VN/8))
KaaE + MKC+
5HVVC> + +33CVMKd+ 5V
33x
K
(0(s am. (AN
h= MEMKE
2d 2d (VN/8')
4
HMKaSE + GH
55HVC0 + +3HCVMKd bV
33K
H
(et((A)))
det(A
x
log
M M/++ +2 +1
MK
det(AI)
det(AI)
h=1
2d 2d (VN/8')
HMKage + 6HH 5HVaCa + +3HCVMKd + 5V
33K
3
x ((llgg(( MK/ + 1)M
2 MKdlog(1 +K//d)
=
+ K) + HHHMM VK)))
(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 (b)()) < 1, the last equality follows from V3k 20H vdC + 12H{VMKK MKd 3. which
16
define in Lemma F.4.
The probability calculation is same as that in Appendix D.2. By combining Terms (iiii together, get that the final regret bound for CoopTS-LMC in misspecified setting
ō 3(d c 12 V ( dMy+ + VK) + d H dMT+ VK)().
with probability at least - 8. Here we finish the proof.
G Proof of the Regret Bound for CoopTS-PHE
Before getting the regret bound for CoopTS-PHE, first present some essential technical lemmas required for our analysis.
G.1 Supporting Lemmas
Proposition G.1. The difference between the perturbed estimated parameter w kin estimated parameter wikk m.h satisfies the Gaussian distribution,
and unperturbed m.h
Shin h.a we m.h ~ . (1(0,, o (Ah, ()) m.h
where wi m. = (A m. (.) estimated parameter.
Σ (Eddrd
[Tn + Vk
m,h+ (bs))
(4)) is the unperturbed
Next we will define some good events that hold with high probability to help prove the critical lemmas in this section.
46

---

Lemma G.2 (Good events). For any fixed 0 < 8 < 1, with some constant > 0, we define the following random events
g (C. def
S scovaj.
max NEiN
A
9(M, K H
def
n S (S, mEM &S
NSH
where eo Then the event ( K, H, occurs with probability least 1-6.
Lemma G.3. Let in Algorithm 2. For any fixed < < 1, conditioned on the event
G(M,K, K, H), with probability 6, for all (m, E M x [K] [M], we have
Σ
D(s (') mA,+ PAV (8), (d,
3H VaDs.
(st,a', (Eu (k)
where we define D3 log(K K + + log (0v2K(2H
+ log 1 1/2
Lemma G.4. Let À = 1 in Algorithm 2. Under Definition 4.1, 1, for any fixed O < ā < 1, conditioned on the event ((M, K, H, 5), with probability (s, a) E S x A, we have
for all (m, k h) E M x [K] [H] and for any
((s,a) a) m.h ra(s, a) Ps Pa (1 5HvdDs |b(( (A
(G.1)
Algorithm and set co +(1). Under Definition 4.1, conditioned on the event G(M, K, H, 8), with probability least 1 ((E))le)) - where C(=) < (3/e)², for all (m, k h) E M [K] x [H] and for all (s, a) E S x A, we have
Lemma G.5 (Optimism). Let
(s, a) I Age,
where A, = =i=ooo+++5vvDD = Ō(Hd).
Lemma G.6 (Error bound). Let in Algorithm Under Definition 4.1, for any fixed < conditioned on the event (MM, K, H, 6), with probability 1 - 6, for all (m, k. h) E M x [K] x [H]
and for any (s, a) E S x A, we have
1 (s, (ssa)) a) S ccHHdlll(s.a))) m.
where 02 = Ō(1)
G.2 Regret Analysis
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 the regret decomposition first
K
Regret (Pgret(K) (K) = Σ
V (sth. Villin (s
mE.V k=1
Σ
E [K (Sm, +), Tmin (mm,h) (-1mm,t)))) (5m, sh
MEM k= h=1
ΣΣΣ
Dm,khh Dm,k,,))
MEM k= h=1
(68)
47

---

K
Ex
(Sm, (m, = s
- -mm m, a tmm.
(Giz)
(G.2)
Next, we will bound the above three terms respectively. Bounding Term (i) in (G.2): for the policy o mm, have
ΣΣΣ Ex- (i "), Tm (:, (8m,h) a (m)m 18) smm. SSO. (G.3)
mE.M
This is because by definition "m.h is the greedy policy for Q m,
Bounding Term (ii) in (G.2): that 0 S Q 11 h S H. based on (D.1), for any (m,k, k) h)) E M [K] x [H) we have [Dm.k.h.1 S 2H and 2m I 2H. Note that km,k.h.1 h.1 martingale difference sequence E[Dm, Fm, = 0. By applying Azuma- Nouma-Hoeffding inequality, with probability at least 8/3, we have
K ΣΣΣ MEM k= h=1
Dm.kh. S 2 22/2MH3 log(6/6).
Note that k,,k,h,2 is also martingale difference sequence. By applying Azuma-Hoeffding inequality, with probability at least - 8/3, we have
ΣΣΣ
Dm..n S 2 log(6/)).
By taking union bound, with probability at least 1 - 28/3, we have
K ΣΣΣ
ΣΣΣ Dm.k.d,1
Dm.k S 4 log(6/6).
(G.4)
Bounding Term (iii) in (G.2): conditioned on the event G(M, K, H, 8'), based on Lemma G.6 and
Lemma G.5, by taking union bound, with probability at least (C(=)lc)) 8 MHKK'' we have
K H
Ex [1tm (Sm.h 15mm1 =
sth =sth.
the (s (s
mEM km Am
H
Σ
(ApE 1he (st (i)
mE
K
HMKA Σ ΣΣΣ
c2dH (s to am ll (=
mEM k= Am1
det((A
det(AAk
< HMKAN Age + cndH
log
+1
M M
MK log
det(AI)
det(AI)
h=1
< HHMKApE + ondH H [d(lo([1+ + MK/d) + 1)M /7 M + MK/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, last inequality holds due to Lemma J.2 and the fact that [|]( < 1.
Here we choose d.H. ddMK As Ō( /d/MK) Conditioned on the event G(M, K, H', have
K
Emp [1th (Mm,, (m,))) 1mm,1 St. - 14 N (sth alr,,.) O V vdMK)).
McM km h
(G.5)
48

---

with probability at least 1 (c))l))) -8' MHK8'. Based on Lemma G.2, the event (M, K, H, 8') occurs with probability at least 8'. Therefore, (G.5) occurs with probability at least
(1-8) (C())l( - 8' -HK8).
We set 8' -8/6(MHK + 2) and choose N Clog(6)/ log(co) where Ō then we have (1- 8' ((=))<) - 8 - -HHKO) 2 - 6633.
Combining Terms (iii together: Based (G.3), (G.4) and (G.5). By taking union bound, get that the final regret bound for CoopTS PPOPTS-PHEINN is Odd) (dM /i + VdMK)) with probability at least 1 - 5.
H Proof of Supporting Lemmas in Appendix G
H.1 Proof of Proposition G.1
Proof. Based on (3.5), we can calculate that
< RRn / -1
Σ
((ra(st, + + ).l")) + V (orx+(("")((( Neth
(s' (m
mm.h + (Ah)
Σ
c
h. (s's xeti")
kdn
(H.1)
(ot (alaaaat m..
where w Wm.h
(A (A
( Eett
(alat,")))Umm.a a' kih.
[rn + vk ( (ss .d)) the unperturbed
estimated parameter. Since Ch NN(0,02), for E (K(K)), based on the property of Gaussian
distribution, we have
kl. h
(s) ~ NN ((t
Since chh ~ N000 I)), we can calculate the covariance matrix of the second term in (H.1),
(A Cov
Σ
k.n "
":l."ps''.e (ss)'aa) - xeth" (Amma)
(wl,at,
= -AAmna)- -122
E
(( ((s',a')((s ( d') + A1 (a
(atiatio" (alatto"))emmaal
= =A2(A)))))))
A me (A
=² = (A
It is obvious that the mean of the second term in (H.1) is O. Thus, we have
R.n Sm,h
w Rnn w m. No (0, o² (A (A)))))))
m.h
This completes the proof.
H.2 Proof Lemma G.2
Proof. Recall that in Proposition G. we have
{ (chia) (Atm))
By Lemma J.10, for fixed
[N], with probability at least 6, have
Il A co do log log(d/8).
49

---

By applying union bound over N samples, we have
P
Sm, Ast.. S do² Logdo))oo((/)) 2
No.
BEIN
Now we define 01 log(dNMMKHHO) and we define the event
I (C, 8)
def
max NE[M]
(imiilll S coodj.
Thus for any fixed m, h and k, the event g (S, occurs with a probability of at least 1 - 6/MKH. By taking union bound over all (m, h, k) E M x [M]] [K], we have
K,GM,,KHH,) P
- (S.
2
me. KS KASH
This completes the proof.
H.3
Proof of Lemma G.3
Proof. Based on the result in Lemma D.4, for any (m, h, k) M [H] x [K], we have
W s 2H 2 Mkd/X.
By recalling the construction of A m. it trivial to find that Amin (A 2 X. Conditioned on the event G(M, K, H, 6), we have
V Small S | A Saovd.
Then by triangle inequality, for all E [MV. we obtain the upper bound
R. w m.h
= [ w + c s 211 Mkd/A+ cia /
Based on the result from Lemma J.7 and Lemma J.9, have that, for any 0, and for all (m, k h) E M x [K] x HH), with probability at least 5, we have
Σ
((s' a') [(V m.h+1 - PA m. () (s),
(A (Att
k k+
3(2H / Mkdd/ X c1 /d//
8k2g2
1/2
4H22
log
+ dloo
+ log
+
2
8
A
1/2
A
Mkd/ 01 /d/)) d/2)
2v 2ke
< 2H
log
+ d d
+ log
+
2
Vx
Here set
1,E
H
with probability least 1 5, we have
2V2k
Σ
((s', at) [(Vth, ((s',a)((V
PA PAVK A. (s', (s',a)]
(ot,at,'' Em (k)
(A
1/2
< 2H 2/2 log(K + 1) log
(V22(2HVVM
1
+ loo -
+ H
H
< 33H
(6V3K(H Mkdtoiova)
11 1/2 Here we finish
where we define D3 log K + 1) log the proof.
+log 8
H
50

---

H.4 Proof of Lemma G.4
Proof. This proof is almost same the proof of Lemma D.8 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, 6), with probability 8, we have
Term (i) 1.33 33Vdddillo(s.d)
A)11
Finally, conditioned on the event G(M, K, H, 6), with probability - 6, for all (m,k, k, E M [K] x [H] and for any (s, a) E S A, have
a) w m. rn(s,a)
PAV A (s, a) $ (3HvdDs + HVd+ Va)lo(s.
Here we finish the proof.
H.S Proof Lemma G.5
Proof. Recall from Definition 4.1, we have
a)) + Pn Vk h+ (s, a) = Φ(s, a) O) 0% +
a) (un, Vi, Φ(s,a) T
where w m.h = On + (nn, Vh (n, Note that (S)( 110 I vd and m,411 S
H S H. thus we have
w m
S 0 Kp V slll
$ Vd HVd
$ S2HV.. Vd.
Then define the regression eтror Aw m. wht mih and any (s, a) S A, we have t (s, a) (s a) + P V M
w m. For any (m,h,k) E M x [M] [K]
(s,
=s,(s, a) Pr v mii+( (5, min (H h 1, max a) (w Wmih Smith }} nE[N]
max { (pss, a) wi when (II h 1), ())
wh wm.h
max ((s, a)s, (i))T(())) (win.. i + Chich) nE(N]
max (0. p68 a)T Aw max ((s,a) a) stem ME[N]
}
Sm.h
(H.2)
where the last inequality holds because [nal & 1 and Vk w Pn vk 14+1(6 (s, a) = Φ(s, T wh. & - 1. Note that [|o(s,, a))l(A )-1 S (I S m.
m.h+1 S H h, this indicates rn a) -
1 for all ((s,a), a). Define C(e) to be a e-cover of {Ø | S 1}. Based on Lemma J.8, we have [C(=) < (3/=)d.
First, for any fixed ((s a) E C(e), we have
{ chi (oCn))~~(0, (At )-1).
Use the property of Gaussian distribution, we obtain
L T she a 1 ( 20 =Q((1).
By taking union bound over n E [N], we obtain
IP( max {Ø shin a1li1AA .20 21 (1- 1 =1 11-60
-11(1-9(-1)~=1--000"
nE[N]
51

---

By applying union bound over C(E), with probability 1 - [c(=)la)' for all Φ E C(s), we have
max nE[N]
{ Φ
Smihh
oll ( 0.
(H.3)
Then, for any Φ = a)s,a), can find ø' E C(e) such that 11 @'1( 1-
(At,)))))
Define
AΦ Φ Φ¹, we have
Φ kknn Φ Aw Aw m.
Sm,h 8¹ Aw min h AΦ Shin - AΦ" Aw mmb
kin
Φ² mmph --11011las poo'llatt,.n a Awth mn Att. - -110Øl ) /|Sstiiilla
[ A mik lat
2 Φ¹ Smi -110511 (aaaaattnn |l mith
-(I + +ll ii lA
(H.4)
Conditioned on the event g(M, K, H, 6), we have
|| 1| Aenn Sciavd
For any vector x E TRdd we have
A Aw m.
x (w w wh...))
= =x (A -1 Amm w mit
E (otia', JEu
(rn + Vok Vintti (d'))((s", (o))
Kc(A))
x STAAA
Σ (bs' (' (a)) w + tww m.h
xO(A))
Σ
[rk v
m1 (5 v ((((ss))
k0(K)
= x (A
- wht mi,h +
Σ
Vak mmt ()"))o((),))))
m1++1
where the third equality holds due the definition of A a We set = A m. Aw m.n- By using Cauchy-Schwarz inequality, we have
(C(A)
-ww T (whh + mih
T(
Awwk w...hlle A+t. min
Σ
V
V
m.h+1
(C(A))
Aw wow.aallas
wit in
Σ
Vk n (s")) ( al)
(At (A
This indicates that with probability least 1 1- 8, for all (m, h, E MX [H] [K]. we have
x((R))
Aw Awm.illl.
< l| m (At a
+
[PP P vb
m.h+1 - V/ Vhh ( (
(AL
1=1
< w/whh +3HdDDs
5HH /H.ddDa
where the second inequality holds because of Lemma G.3. Then for all (m, h, E M x [M]] x [K], with probability at least - 6, (H.4) becomes
{Ø ck. - $ Awt [N[N]
max
52

---

max { TT Sh - 1 ( - m.nll A... - ---eoa 5H 5HHvdD.) [N[N]
this is achievable through calculation. Define A, Govd 5H VdDs ((H)). Then, for all (m,h,k) E M x [M] x [K], with probability at least 1 - Ó, we have
Now we choose Ö(Hvd) and guarantee that o > 5H VHVdDs 2 | m.k m.s
A
{
Sm,h Φ Aw mm
k,n
max {Ø' phin o (l AsE. DE[M]
max ne[N]
Recall from (H.3), by taking union bound, with probability at least - (C(s)lc8 - 5, for all (m,h,)) E M [
[K] and for (8,a) ES A, we have
{Ø T Sm, $ T m.mk 2 Ase. NC[N]
max
Finally, recall from (H.2), we have, with probability at least - IC(=)lc3 6, for all (m, h, k) M x [H] x [K] and for all as, E 8 x A. we have
c (s, < AsE.
This completes the proof.
H.6 Proof of Lemma G.6
Proof. Recall the definition of model prediction error Definition D.1, we get
-1 mm, a) = (s, (s, a) (wh Shith
1r, V m,h+1
(m,,)))ss,))) (s,a)
= =min max ((s,
H - h h11 -rh(s,a) - Ph Pa
(8.
nE(N]
< max a (w mih + nE[M]
ckin) Smit)
(n(ss,a) - PP Vr miht1 (s,
max (bs, a) - (ra(s,a) + 1 (s, $ a) T nE[M]
< (s, a) Pa Vk M4. (8, a(s,a) w Tw m.h + max ( a)T aE(N]
Sma.i T
Based on Lemma G.4, conditioned on the event (MM, K, H, 6), with probability 1 - 5, for all h) [K] [H] and for any (s,a)
A, have
((s,a) a)
w m. (s, - Pr VA (n, a) < SHVaDalló(s.a))l
(H.5)
Conditioned on the event G(M, K, H)) for all (m, k) E Mx [H] x [K] and for any (s, a) E S A, we have
max EM
(bs8a)
km S cooValll ())
(H.6)
Combine (H.5) and (H.6), then use defined in Lemma G.5. Conditioned on the event g(M, K, H,8), with probability for all (m, h, k) E M [H] [K] and for any (s, S A, get
mm. (s, (5H /d + a [[o(s, a) ()
c2Hd Φ a) A+ 11
where = Ō(). Here we completes the proof.
I Proof of the Regret Bound for CoopTS-PHE in Misspecified Setting
In this section, we prove the regret bound for CoopTS-PHE in 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 Here we mainly point out the differences of proof between these two settings.
53

---

I.1 Supporting Lemmas
Lemma 1.1. Let À 1 in Algorithm 2. Under Definition 4.8, for any fixed 0 < 8 < 1. conditioned on the event ([M, K, 11, with probability 1 6, for all (m, E M [K] [H] and for any (8, a) ESS A, we have
((s,a)' Wm.t - (s) - PA v (s, & (5HvāDs + MHLVMMddlllss.ooo
3HC, (LI)
where D3 is defined in Lemma G.3.
Proof of Lemma I.I. 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
[Tem((i) s 3HVaDsllobs,.o a))(a
Finally we can get the desired result.
Lemma I,2 (Optimism), Let
in Algorithm 2 and set co (()). Under Definition 4.8.
conditioned on the event G(M, K. H,5), 8), with probability at least 1 [C())lc) where C(e) < (3/e)², for all (m, k, h) E M x [K] x [H] and for all (8, a) E S x A. we have
I S AgE + +HC.
where As = =o==
((Hd)
Proof of Lemma 1.2. This proof is similar to the proof in Appendix H.5. In the previous part, we have defined
Am,1 = Fm, h V n (s, a) ()s, (pr, V Vii
A,, = Tm, (s, a) Φ(s,a) T
where Am.1 < 2HC and Am, S Thus we have
Tm, a) + P Pm
V mm.h+i (s, = a) T wm., + Am,1 + Am,.
where wk m. (pan, Vh h 1) + On. Then we define Awk mihh w wk m.he For any (m, h, k)
M x [H] x [K] and any (5, S A, we have
m, (8. a) (s, a) + Pm. Vk m. (8, a)
(s,
= =mm,hss a) + Pm.. m. (s, min H htt 1, max o(s a) (wi., + R.n
nE[N]
max (p(s wht (H - h 1), Ø(s, wht max Φ a(s,a) ((s,,)T(wr)) (wh. (Wmmh + Smih
kkn
}
nE[N]
+ Am,1 + Am,
< <max {0, (bs a) Aw max ((s,a) =E[N]
ck.z Sm,h
+HC.
(1.2)
In Appendix H.5, we have proved that with probability at least 1 (C(E)lo0) - 8, for all (m, h. k)
M [ x [K] and for all (s, S A, we have
(6 T The o T Aw m.h 2 -Ags.
max NE(N]
Substitute it into (I.2),
get the final result.
Lemma 1.3 (Error bound), Let À = 1 in Algorithm 2. Under Definition 4.8, for any fixed < 8 < conditioned on the event (MM, K, H. d), with probability 1 ó, for all (m, h) M x [K] [H]
and for any (s, a) E S x A. we have
u (s. a) < (c2Hd 3HC/MKK))l(s.)))ll....
3HC.
where 02 = Ō(1) is same that in Lemma G.6.
54

---

Proof of Lemma 1.3, Similar to the proof in Appendix H.6, using (H.6) in Appendix H.6 and (I.1), we have
b m. (s, a) - (s a) + Pv (1,441(8,)) Φ(8, a)
w
m.h
+ max nE(N]
[ a)
ck.n Sm,hh
(()(a)))))) 33H
- (c2Hd 3HC (00 +331,,
where = (1) is same that in Lemma G.6. Here we completes the proof.
1.2
Regret Analysis
In this part, give out the proof of Theorem 4.10, the regret bound for CoopTS-PHE in the misspecified setting.
Proof of Theorem 4.10. This proof almost same as the proof in Appendix G.2. We do the same regret decomposition (G.2) and obtain the same bound for Term (i) (G.3) and Term (ii) (G.4). Next we bound Term (iii) with new lemmas in misspecified setting.
Bounding Term (iii) in (G.2): conditioned on the event ( K, H, 8'), based on Lemma I.3 and Lemma 1.2, by taking union bound, with probability at least 1 - [C(s) - 5' - MHK'', we have
K
(Ex- (
(sm, am,h) 8m,11 smm.]
1h in (stm. a)m.))
K
H
(st ofn Agre + +3HC)
mEM R= hmm
K
H
(ozdH 3HC ( + +3H Agre + +3HC)
MEM
HMMAAES+ 6FM (c2dH +
| mn Ila (-
h= MEM k=
< HMKKAM + MKG + (c2dH+ + +3HCVMKO)
det(AR) de((AT))
+1) MVT+ +2 21 MK log
det( del(AT)
log
< HMKANe -HH (c2dH + 1-HHVMMM
x 11
1)M + 2/ M MKdlog(L + MMK/d)
= -6 (V VK) dHH dM VK).).
The first inequality follows from Lemma 1.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 (lo(-))l2 S L, and again we choose dH / d//K AAg = (d)dKK))
The probability calculation is we get that the final regret bound for CoopTS--PHB in misspecified setting
that in Appendix G.2. By combining Terms (ii) together,
Regret K) = 5 ( H2MM (V VK) AHH ( VdM + vK)S).
with probability at least 1- 8. Herr finish the proof.
55

---

Auxiliary Lemmas
Lemma J.1. [1. Lemma 11] Let (X,)== be a sequence in IR V is x d positive definite matrix
and define V, +V+ X Then, we have that
det((Vn) det(V)
log
X X v
Further, if Xx||2 1 L for all 1, then
Σ min 1, X bl .} - 2( log (x)) - log det V)
S 2(d (( ((race(V) + / log det V),
and finally, if Aina (V) max (1, L2) then
1x S 2 log det (V,(
det(V))
Lemma J.2. [1, Lemma 10] Suppose X₁, X2..... X₁ E Ie and for any s s St. | S L.
Let V, XI XI Σ X,X, for some À 0. Then,
det { (A+
S
Lemma J.3. [32, Lemma D.5] Let A E Rdddd be a positive definite matrix where its largest eigenvalue Amax(A) S A. Let X1, Xy be vectors in Rd. Then it holds that
k
1/2
S VAk
Σ
xx 1xil
X;
Lemma J.4. [36, Lemma D.1] Let A, holds that
XI + Ei=1 ΦiΦ. where Φ; E Rd and À > 0. Then it
Σ Φ (A.)) Φ. S d.
1=1
Lemma J.5. [33, Lemma D.1] Given multivariate normal distribution X N (0, E), have,
P
X S (x(z)
2 1 -
Lemma J.6. [30] If A and B positive semi-definite square matrices of the same size, then
S [tr( 2 < tr (A2) tr (B²) s (tr(A))(tr(B)))
Lemma J.7. [36, Lemma D.4] Let { be a stochastic process on state space S with corre-
sponding filtration (F.) Let {Φ, 00 be vaduud stochastic process where & Fi-1, 1, and
|ob.l| < 1. Let A₃ = +I E O.0, Then for any 5 > O, with probability at least for all H, we have
k 0, and any V E V with sup.es [v))
d log
k +
A
N
2
Σ (VV))))(((s))
(V()) F F=-1l)
<
2
log
2
A-
where Ng is the e-covering number of y with respect to the distance dist(V, V') = sup (s()) V*(s)].
Lemma J.8. [75, Covering number of Euclidean ball] For any 0. Ns. the e-covering number of the Euclidean ball of radius B > 0 in IRd satisfies
2B
d
3B
N z 1+
5
8
56

---

Lemma J.9. Let V denote class of functions mapping from S to R with the following parametric form
(() max min max O a) w" w -- -
where the parameter w" satisifies ||w S B for all [N] and for all (z, E S A, have [ a)ll S 1. Let Ny.s be the E-covering number of with respect to the distance dist (V, V*) = supses [V()) - (s)). Then
3B
d
Nv.5 S E
Proof. Consider any two functions V1, V/ V with parameters {wi hEE[N] and (w])nel) respec- tively. Then we have
dV,, 1/2) S sup
max ( () T w max ((8,a) ww" [N(N]
9,a
=E[N]
S sup
max ne(N]
(688, a)
w (588 a) (aaT)//] w3
8,0
sup
Φ w" Φ w/
|
nE(N]
1 T (w" w()
sup
nE(N]
max
sup ||ll|| w"
w
nE[N]
max
wT w2
nE[N]
Let Nw.e denote the E-covering number of {w E R
|||| S
B}.
Then, Lemma J.8 implies
S 3B d
2B +
Nw.s -
For any Vi E V. we consider its corresponding parameters [WT]ne(N) For any E [N], we can find w such that |[w"" will S E, then we can get V/2 E V with parameters (w])ne(M)- Then have dist V2) S max l|w" w Thus, have,
1+ 2B
3B
Nv.e S Nw.e <
This completes the proof.
Lemma J.10. [3] Suppose Gaussian random variable Z NN 02), where a 0. For
0 < 1, we have
P > P( 20) 2
2,
PPZ < 200 2
V8T
v V8T
And for 2 2 1, we have
- 12
2/2
S P(IZ - 11 20) <
22
2/T
Lemma J.11. [32, Lemma D.2] AAAAAA-) where A is a scalar. Let m. .,...., uN be N independent samples from the dis- tribution. Then for any
Consider d-dimensional multivariate normal distribution
IP
max JEMM
|nl1 S <e/dAlog(d/o)) 2 - 16
where e 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
x Ax
del(A)
sup x
x Bx det(BB)
57

---

1000
82
SN
r
Figure 3: The N-Chain environment [62].
K Additional Experimental Details
We conduct comprehensive experiments investigating the exploration strategies for DQN under 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: Coop'SS-PHE: as "PHE" and CooPTS-LMMC "LMC" in experimental contexts and figures. In addition to methods, the baselines we selected are either commonly used (DQN [57]. DDQN [28]) or with competitive empirical performance (Bootstrapped DQN [62], NoisyNet DQN [26]). Both Bootstrapped DQN and NoisyNet DQN are randomized exploration methods. Bootstrapped DQN uses finite ensembles generate the randomized value functions and views them as approximate posterior samples of Q-value functions. NoisyNet DQN injects noise into the parameters of neural networks to aid efficient exploration. For those figures which aim to compare among different m agents within a single plot, we use Total Episodes to indicate the total number of training samples for a direct comparison. Note that the shaded areas on all figures represent the standard deviation.
Table 2: The swept hyper parameters in N-Chain for PHE
Hyper-panee parameter
Values
Learning Rate 7)k
(10-1,3x10-2 10 10-300-3300 10 10-1) {1,2,4,8)
No Target Networks
Reward Noise
10 10,10-110-3,101
Regularization Noise
1.0)
Table 3: The swept hyper-parameters N-Chain for LMC
Values
Learning Rate 7ek
{10-1,3x 10-2, 1,0, 10 1,0x,00 10 1001 (1.0, 0.1, 0.01}
Bias Factor a Inverse Temperature Bmnk
(109, 102 10 10 10*)
No Update Jr
11,4,16,32)
K.1 N-chain
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 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.
Subsequently, provide more comprehensive study 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 E {1, 2, 3, 4).
We list the details of all swept hyper paremeerrssserss in N-chain for PHE and LMC in Table 2 and Table respectively. Specifically, PHE is trained with reward noise E,
k.I.a 10-2 and regularizer noise
58

---

Table 4: Hyper-parameters used in the N-chain
Hyper-parameter
PHE
LMC
DQN
Bootstrapped Noisy
DDQN
DQN
DQN
Discount Factor À
0.99
0.99
0.99
0.99
0.99
0.99
Learning Rate 7
3 x 10-2
10-4
3 x 10-2 Relu Linear
x 10-2
3 X 10-2
3 x 10-2 Relu
Hidden Activation
Relu Linear
Relu Linear
Relu
Relu Linear
Output Activation
Linear
Linear
No Update Ju
4
No Target Networks
2
4
Batch Size
32
32
32
32
32
32
NN size
32
32
32 32
32
32
32
32
32
32
32 32
Episode Return
Episode Return
Episode Return
PHE
DON
DON
Restamppodd DON Kelekie CON
WANNin CON
WalRii CON
200M
200N
DOON
Training Episodes Agent (a) m=2
Training Episodes Agent
Training Episodes Agent (c) m=4
(b) m=3
Figure 4: Comparison among different exploration strategies in N-chain with N 25. All results averaged over 10 runs.
Sh 10-3 in (3.5) and LMC is trained with Bm.. = 102 and in (3.7) and optimized by Adam used in Performance Consistency with Varying m In the investigation detailed in Figure 5, we explore parallel learning without inter-agent communication. Note that the z-axis implies the total training episodes from agents. Consequently, while multiple agents engage in simultancous policy learning, each agent independently formulates its policies without the exchange of transition information. The discernible trend in this scenario is that 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.
SGLD [33] with 01 = 0.9, 022 0.999 and bias factor = 0.1. The final N-chain are presented Table
8
Episode Return
Episode Return
1,
N
10
m 2, 10
m
m 3,
2500
2000
Total Episodes
Total Episodes
(a) PHE
(b) LMC
Figure 5: Rewards with averaged over 10 independent runs for different numbers of agents among algorithms without communication. Note that when one agent indicates centralized setting.
59

---

Episode Return
Epicode Return
Episode
centraland (nnar)
cettreeed 30
camrioss.
spectti
bward ageenn contortit
orstanti aquntal
LOTSLANCS agarai.
desovendial2 upento. m
eppassaal spentat 10
aesurentall uparol,
Total Episodes
Total Episodes
Total Episodes
(a) m=
(b) m=3
(c) m=4
Episade Return
Episode Return
2.
Epleade Return
cotookad =10
centalted
owmiiss,
cecereaneceee aporto. 1 =2 baan agandi
commrnacaa.oo agarial
recommenaatoe upantal contratte occonentall agannt, nin Total Episades (l) m=4
commano agamnt
upantalin
esponondat2 agenen 10
250
Total Episades
ns 1999 thee
Total Episodes
1208 3000
(d) m=2
(e) m=3
Figure 6: Different number of agents m with different synchronization strategies as well as the single-agent and communication settings in N 10. Top: PHE, Bottom: LMC
14
Episade Return
Episode Return
Epl sods Ratur
LBC
UMC
LMC He MacaTT
mtt
heurat's Pne
keunfTs
Uniks
<21
Episodes
2033
Episodes
Episodes
(a) m=2
(b) m=3
(c) m=4
Figure 7: Performance with different number of agents m compared with hundit-inspired exploration in N 10.
Different Synchronization Conditions To further demonstrate the efficiency of parallel learning with communication, we compare different synchronization conditions Section 3. Specifically, denote synchronization (1) in every constant step constant, (2) following exponential func- tion as exponential, and (3) based on (3.3) as linear. To have a fair comparison among different synchronization conditions, 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 similar number of synchronization. Figure illustrates that any synchronization condition can improve learning efficiency but still with centralized learning as an upper bound. Note that the --axis implies the total training episodes from m agents.
Performance Compared with Bandit-inspired Methods Since one of our proposed random exploration strategies, PHE variant of approximation TS, 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 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 z-axis implies the total training episodes from agents.
60

---

PHE
Computation Time (sec)
30-
LMC
DQN
Bootstrapped DQN
NoisyNet DQN
DDQN
20
NeuralTS
NeuralUCB
10
32_2
32_3
64_2
64
Neural Network
Figure 8: Computation time with different exploration strategies.
10
10
temp
temp 1e2
inv temp led
Episode Return
Episode Return
0
temp 1e6
temp 1e8
temp
inv temp 1e2
inv temp Ic4
inv temp 1e6
temp 1e8
1500
Training Episodes per Agent
Training Episodes per Agent
(a) m=1 (centralized), N=25
(b) m=2 (no communication), N=25
Figure 9: Hyper-paramann tuning of inverse temperature (inv temp) 3m,, for LMC with N = 25: (a)
centralized setting m (b) agents without communication m 2.
Computational Time We have demonstrated that both NeuralTS and NeuralUCB exhibit conver- gence performance levels comparable our proposed randomized exploration strategies (i.e., PHE and LMC) when considering the case of N = 10 with m = under the synchronization condition (linear), 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
10 and m 4 over 10a steps with varying neural network sizes, such [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 more complex problems with larger neural networks.
Hyper-parameter Tuning Inverse Temperature 3m.k Subsequently, we scale the problem to N 25. Given the extended horizon, the demand for exploration intensifies, leading to conduct
61

---

Episode Return
Episode Return
N 25, buffer
1. full buffer
m 1. 25, half butter
m 1. 25. half buffer
1. 25, buffer
communi cation), 25, buffer
|no communicationl, N
butfer (no communication), N = 25, half buffer
(no communication N 25, half buffer
m [no communi cation)),, 25, less buffer
m (no communication), N 25, less buffer
1000
2000
3000
4000
5000
6000
1000
2000
3000
4000
5000
6000
Total Episodes
Total Episodes
(a) PHE
(b) LMC
Figure 10: Different buffer size with N 25 between single agent (centralized) and 2 agents (no communication). Note that the full buffer indicates the size of the total episodes. Each agent in no communication setting only occupies half of the total episodes. Therefore, two curves (full buffer, half buffer) in no communication are consistent.
10
10
Episode Return
Episode Return
(centralized))
(no communication), 25
2 (no communication), 25
m 2 (lneea)), N - 25
2 (linear), - 25
m (constant), (exponential), 25
(constant), (exponential), 25
1000
3000 Total Episodes
2000
4000
5000
2000
3000
4000
6000
Total Episodes
(a) PHE
(b) LMC
Figure 11: Different synchronization strategies as well as the single-agent and no communication settings in N 25.
hyper-parametes tuning for the inverse temperature parameter 3m.k in LMC, as illustrated Figure 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 discernible gap between centralized and parallel learning, departure from the pattern observed in Figure 5. We posit that the disparity may stem from issues associated with the replay buffer size 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 performance comparison be- tween 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 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 We conclude that linear condition results in competitive performance in both PHE and LMC in the --ahain problem and we report all exploration strategies with linear condition in
62

---

Episode Return
8
m 1 (centralized), prioritized
m communication), prioritized
m 2 (linear), prioritized
m 1 (centralized)
communication)
2 (linear)
1000
2000
3000
4000
5000
6000
Total Episodes
Figure Gap reduction improvement with prioritized experience replay for parallel learning without communication. Note that the same settings with standard and prioritized experience replay are in the same-ish color.
MOBLO
FINE
R:00
201
DRAA
SuperMarioBros-I B----- SuperMarioBros-Iee (-)-(cc)
SuperMarioBros 1-3-(d) SuperMarioBros 1-4-
vO
v0
v0
v0
Figure 13: Illustrations of 4 different environments in Super Mario Bros task.
Section 5.1. Note that the r-axis Figure 10 and Figure 11 represent the total training episodes from m agents.
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 r-axis repre- sents the total training episodes from 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/ are based on standard experience replay because standard sampling linear condition has similar performance against PER with faster training time.
K.2 Super Mario Bros
While cooperative parallel learning enhances training efficiency through data sharing, challenges emerge when handling data from devices capturing images audio due to privacy concerns in real- world applications. response, our approach extends randomized exploration strategies federated reinforeement 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 to update Q functions with horizon h E H. However, in practice, we can directly update the weight of the neural network reduce the communication cost.
63

---

Table 5: Hyper-parameters used in the Super Mario Bros
Hyper-parameter
PHE
LMC
DQN
Bootstrapped Noisy
DDQN
DQN
DQN
Discount Factor X
0.9
0.9
0.9
0.9
0.9
0.9
Learning Rate 7
10 10-2
3 x 10-4
10-2
10-2
10-2
10-2
Hidden Activation
Relu Linear
Relu
Relu Linear
Relu
Relu
Relu
Output Activation
Linear
Linear
Linear
Linear
No Update Ju
4
No Target Networks
2
4
Batch Size
32
32
32
32
32
32
The training process unfolds within a federated reinforcement learning framework, wherein local updates and global aggregations iteratively executed [37]. Specifically, each agent iterates through multiple local updates 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 fully connected layers with the output of action space in the Q network. The detailed ayper-parametent for Super Mario Bros task are presented in Table 5.
Algorithm 4 Unified Algorithm Framework for Randomized Exploration in Federated I Learning
for episode 1..... K do for agent m .M do
2:
3: Receive initial state $
4: VE mm, +-
5:
( ( Randomizzd Exploration for step h = 1,..., H do ar,,.. f argmaxxcc Q (s (s a).
< Algorithm 2 Algorithm
6:
7:
8:
Receive stn sm, and rh-
if Conddiiion then SYNCHRONIZE True. 11: end if
9:
end for
13:
end for
if SYNCHRONIZE then
15:
for step h H. H...., 1 do
2hh ΣM Q
16:
17:
Qh + Q Vm
end for
19:
end if
20:
end for
K.3 Thermal Control of Building Energy Systems
BuildingEnv encompasses the regulation of heat flow in multi-zone building to sustain desired temperature setpoint. We focus on one pre-defined building called "office small" different cities with varying weather types, iee,, Tampa (Hot Humid), Tucson (Hot Dry), Rochester (Cold Humid), and Great Falls (Cold Dry). Each episode is designed to span single day, comprising 5-minute time intervals (H 288, 5/60 hours).
64

---

Table 6: Hyper-parameters used in the building energy systems
PHE
LMC
DQN
Bootstrapped Noisy
DDQN
DQN
DQN
Discount Factor
0.99
0.99
0.99
0.99
0.99
0.99
Learning Rate y/s
10-
3 10-3 Relu
3 10
3 x 10
3 x 10-3 Relu
3 x 10-3
Hidden Activation
Relu
Relu Linear
Relu Linear
Relu
Output Activation
Linear
Linear
Linear
Linear
No Update Ja
8
1
1
No Target Networks
1
I
Batch Size
32
32
32
32
32
32
NN size
64
x 64
64 64
64 64
64 x 64
64 64
64 64
-15
-10
-20
Daly hutur
20
Daily Betuum
-35
-50
Random
Noisstrappeccda//ec
DDON
Random
BottarespeaNciyhit DOON
Algorihhm
(a) Tampa (hot humid)
(b) Tucson (hot dry)
-60
-50
Daiy Barum
Daily feeum
-30
1100
-30
-150
-100
-200
PHE
syd
Bostebrappedkckllet
DD0K
Algorithm
Algorithm
(c) Rochester (cold humid)
(d) Great Falls (cold dry)
Figure 14: Evaluation performance at different cities in building energy systems
Observation Space The state at time step f, denoted st) M+4 encompasses the temper- atures T.(t) of each zone, where i E M, along with four additional properties: QCHI (t), (P),,, Tt))), and (t).). Specifically, QtH((L) represents the heat gain from solar irradiance, (t()) de- notes the heat acquired from occupant activities, while (t( and (() signify the ground and outdoor environment temperatures, respectively.
Action Space The continuous version the action a(t) E [-1, M controls the heating of M zones. However, since randomized exploration strategies DQN [57] as the backbone, 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 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 - [12 -31 (argett) - T(t)
where (taget (1) [T bagg (L), T Thurget (!) are the target temperatures and T()) [Ti (1), (2))), .... TM (1) are the actual zonal temperatures. The parameter is the trade-off be- tween the energy consumption and temperature deviation penalties.
65

---

We execute experiments following the united framework in Algorithm 1, synchronizing every constant number of steps across diverse weather conditions in varying cities. The 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 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 more challenging cold weather conditions compared to hot weather conditions.
we used
66

---

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

---

Answer: [Yes]
Justification: We present theoretical analyses of our algorithms in the linear structure under the assumption of linear function approximation and linear MDP setting in Section 3. We provide comprchensive proof from Appendix B to Appendix including the analysis the communication complexity, proof of the regret bound for two proposed methods, misspecified setting, and all supporting lemmas.
Guidelines:
The answer NA means that the paper does include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
We describe experiment settings and environments with the main experiment results in Section 5 and mention the hardware we run on. In addition, the used archi- tectures and bypaeeparameters are provided Appendix K. We also release our code in supplementary materials.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
68

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification: We provide code in supplementary materials and in the link in Section 5. Specifically, we provide scripts and access to the catasets/environments we use.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (uttps://nips cc/
wttpuuuiiissooooooioioooooo for more details. Ieliii/gguides/ooeeuuiie
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: / //nips. ctaiss.cc/ublii. /ww.d/uissee//ee. CodeSubmi ssionpolicy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We present the goals, main settings, and the datasets/enviromments in Section 5. Due the space limit, the full training details are provided in Appendix K.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: We present our learning curves in the figures with shaded areas, representing the standard deviation over varying random seeds. In addition, violin plots can display the distribution of the return with probability density.
69

---

Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by enror bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the eπror bar is the standard deviation or the standard error of the mean.
It is OK to report I-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (c.g. negative error rates).
show in tables
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
Question:
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [Yes]
Justification:
We indicate related description in Section
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https htt//enurip.ece httppp//....p......c.cccttteeee.
Answer: [Yes]
Justification:
We do review and follow the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive socictal impacts and negative societal impacts of the work performed?
Answer: [NA]
70

---

This paper presents work whose goal is to advance the field of Reinforcement Learning. This work does not have any potential negative social impacts.
Justification:
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has socictal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our work does not include and release new data, so the paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We have cited and the original paper that produced the code package and dataset. In addition, we also provide the URL in the README.md.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
71

---

The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g.. website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if it has changed) should provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
We do not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/mooel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: This paper is mainly for proposing provable and practical algorithms without any human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper is mainly for proposing provable and practical algorithms without any human subjects.
72

---

Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
73


Reviews:
[{"review_id": "ZjjJiNBlKC", "reviewer": "Reviewer_CHJv", "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.", "questions": "- Could you provide a more detailed explanation for the configuration of the contenders?\n- Could you provide a more detailed explanation for the discrepancy between the theoretical guarantees and the experimental results?\n- How should the parameter $\\gamma$ be set in practice?", "limitations": "I do not find the negative societal impact of this work.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "-  Although the results of this paper are not entirely new, as they extend randomized exploration methods from the single-agent to the cooperative multi-agent setting, the authors effectively highlight the technical challenges and their contributions (line 227-236).\n- The algorithm proposed in this paper have better communication complexity than the UCB-type algorithm in the synchronous setting.\n-  Extensive experiments are conducted to validate the effectiveness of the proposed method, which is an advantage for a theoretically oriented paper.", "weaknesses": "- 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. \n\n- 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).\n\n- Parameter setting: It appears that setting the threshold $\\gamma$ requires knowledge of $K$. How should this parameter be set in practice?\n\nOverall, 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable time and effort in providing detailed feedback on our work. We hope our response will fully address all of your points. \n\n---\n### Q1. Explanation for the configuration of the contenders\n\nAll the baselines as well as our two proposed methods are run under the unified framework in Algorithm 1 for fair comparison. The only difference is how they explore. For example, the vanilla DQN follows $\\epsilon$-greedy exploration strategy, but it is still equipped with the synchronized steps in your suggestion. We will emphasize this more in our final version of the manuscript. In addition to using a unified framework for all DQN baselines and our exploration strategies, the architecture for all of them remains consistent. Specifically, we detail the number of neural networks and layers for each task, as well as our hyper-parameter tuning process in Appendix Section L: Additional Experimental Details.\n\nIt is generally observed that performance drops in a multi-agent parallel learning setting compared to a single-agent setting for all DQN-based approaches, including our two proposed strategies. This phenomenon is anticipated, as Theorems 4.2 and 4.4 indicate that regret increases with $\\sqrt{M}$. Consequently, the single-agent performance serves as an upper bound for multi-agent parallel learning. In other words, empirical performance may decline with increasing $M$, regardless of the exploration strategy, as demonstrated by Bootstrapped DQN in this specific task. Our empirical results corroborate our theoretical findings.\n\nWe would like to emphasize that the goal of our unified framework is to solve a single task efficiently when computational resources are limited. In this context, multiple agents can share the computational burden and accelerate training within our framework. CoopTS-PHE and CoopTS-LMC, combined with our synchronization conditions, facilitate efficient synchronization with minimal communication complexity.\n\n\n---\n### Q2. Explanation of the experimental results\n\nFirst, we clarify that both Theorem 4.2 (CoopTS-PHE) and Theorem 4.4 (CoopTS-LMC) show that the cumulative regret has the order of $\\sqrt{M}$. Thus the average regret (defined as the cumulative regret divided by the number of agents) has the order of $\\sqrt{1/M}$, meaning the average regret decreases when $M$ is larger, which indicates that the average performance improves when $M$ is larger. We would like to clarify that the plots in Figure 1 and Figure 4 in the original manuscript do not directly imply a convergence rate comparison between different numbers of agents due to the x-axis scaling.\n\nIn particular, we appreciate the reviewer's observation regarding the x-axis scaling in the figures. These differing scales were intended to present comprehensive results. Specifically, our x-axis indicates the comparison from a sample efficiency perspective, which represents the total number of episodes shared among all agents, as mentioned in Line 274. Therefore, we can have a better understanding of how different RL algorithms perform with the same number of agents. To compare the convergence rate across settings with different numbers of agents, we should divide the x-axis by the number of agents involved in training. Please refer to Figure 1 in the attached PDF, where the y-axis is the average reward among all agents and the x-axis is the number of training episodes per agent. From this perspective, the convergence rate in Figure 1(b) is not slower than in Figure 1(a), especially that CoopTS-LMC has a significantly faster convergence rate when $n=3$ in Figure 1 (b). This indicates consistency with our theoretical results. We will update the plots in the final manuscript to ensure consistent scaling and enhance clarity.\n\n\n---\n### Q3. Practical setting of parameter $\\gamma$\n\nWe agree that there may be additional hyper-parameter tuning for $\\gamma$ selection. There are prior works in the single-agent setting for all the experiments we conduct. Therefore, we set the initial total number of episodes among all agents $K$ based on prior works in single-agent settings. This initial setting of $K$ is used to decide our $\\gamma$, followed by further fine-tuning of $K$ depending on the initial performance. We acknowledge that generalizing the synchronization rule from equation (3.3) to varying tasks may require more effort, despite its simple theoretical proof. As mentioned in Line 142, we actually investigated three types of synchronization rules in our experiments, including the rule from equation (3.3). Figure 6 demonstrates the results on the $N$-chain problem, indicating that all three synchronization rules perform consistently when $N=10$. Furthermore, Figure 11 shows a relatively better performance using the synchronization condition from equation (3.3) shown as the green curve when $N=25$. However, we recognize the practical value of the simplicity of other synchronization rules, which do not require knowledge of $K$ and result in closer performance. This flexibility highlights the practical utility of our unified framework.\n\n\n---\nWe hope we have addressed all of your questions/concerns. If you have any further questions, we would be more than happy to answer them and if you don’t, would you kindly consider increasing your score?", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "UDXZ5c3pko", "reviewer": "Reviewer_kfpt", "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.", "questions": "* What is the tradeoff between using perturbed history exploration and Langevin Monte Carlo exploration?", "limitations": "I didn't see potential negative societal impact of this work.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "* The paper is well-written and easy to follow.\n* Theoretical analysis is provided and it can match the performance of the state-of-the-art results with the potential to generalize to deep RL.\n* Experiment validation is provided.", "weaknesses": "* The technical novelty and contribution seem limited. Can authors elaborate on the challenges in the analysis?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable time and effort in providing feedback on our work. We hope our response will fully address all of your points. \n\n---\n### Q1. Detailed explanation about challenges in theoretical analysis.\n\nWe explain the specific improvements we made in our theoretical analysis here.\n\n1. In our theoretical analysis, compared with UCB exploration, randomized exploration encounters more challenges to prove the lemma of optimism (Lemma E.10 and Lemma H.5) and the lemma of error bound (Lemma E.9 and Lemma H.6). For UCB type of algorithms, the property that the optimistic estimated value function is larger than the optimal value function can be directly guaranteed because of the added UCB bonus term. While for randomized exploration (TS-based exploration here), our optimism lemma is to prove a negative model prediction error (defined in Definition E.1). This can not be directly guaranteed because it can only be achieved with a probability. To ensure a high probability result, we use multi-sampling (such as line 3 in Algorithm 3), which causes some difficulty in analysis. \n\n2. The multi-agent setting and the communications from synchronization in our algorithms further increase the challenges in our analysis compared to randomized exploration in the single-agent setting [2, 3]. To upper bound the self-normalized term summation in the multi-agent setting, we prove Lemma E.12, which is a modified and refined version compared with [4].\n\n3. One big theoretical challenge is that we find and fix a non-negligible error in the regret decomposition that previous work ignored (we discuss this in Remark 4.5). To be specific, in proofs for both CoopTS-LMC and CoopTS-PHE we use a new $\\varepsilon$-covering technique to prove that the optimism lemma holds for all $(s, a) \\in \\mathcal{S} \\times \\mathcal{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 [1] that use the same regret decomposition technique in the single-agent setting. Several following works using the same regret decomposition technique also ignore this error. \n\n4. Additionally, in Appendix C, we also provide a refined analysis of communication complexity and achieve the state-of-the-art result. This is an improvement compared with previous work [4] under the same setting. This result matches the asynchronous setting result [5] and we discuss some interesting phenomena in Remark 4.7.\n\nWe hope these illustrations could show our contributions on the theoretical analysis to you more clearly.\n\n---\n### Q2.  The tradeoff between using perturbed history exploration and Langevin Monte Carlo exploration\n\nWe discuss the comparisons between PHE and LMC in the following three aspects: algorithm design, theoretical results and experiments.\n\n1. Algorithm design: For PHE, we add i.i.d. random Gaussian noise to perturb reward and regularizer to realize randomized exploration. This requires a large number of i.i.d. Gaussian noise when the total episode $K$, the horizon length $H$ and the multi-sampling number $N$ are large. For LMC, we do the randomized exploration by performing noisy gradient descent. This requires the convergence of the LMC to the target distribution.\n\n2. Theoretical results: Under linear MDP setting, we notice that CoopTS-PHE (Theorem 4.2) and CoopTS-LMC (Theorem 4.4) have the same order of regret, which is mentioned in Remark 4.5. While under the misspecified setting where the transition functions $P_{m,h}$ and the reward functions $r_{m,h}$ are heterogeneous across MDPs, by comparing Theorems D.3 and D.5, we find the result of CoopTS-LMC has an extra $\\sqrt{d}$ factor worse than that of CoopTS-PHE, causing the chosen $\\zeta$ in CoopTS-PHE has an extra $\\sqrt{d}$ order over that in CoopTS-LMC. This indicates that CoopTS-PHE has better performance tolerance for the misspecified setting (we have discussed in Remark D.6).\n\n3. Experiments: Based on our experimental results, it is hard to say which one exactly outperforms the other one. For example, in Figure 1, we find that CoopTS-LMC performs better in Mario tasks and CoopTS-PHE performs better in N-chain tasks.\n\n---\nWe hope we have addressed all of your questions/concerns. If you have any further questions, we would be more than happy to answer them and if you don’t, would you kindly consider increasing your score?\n\n\n### References:\n\n[1] Cai, Qi, et al. \"Provably efficient exploration in policy optimization.\" International Conference on Machine Learning. PMLR, 2020.\n\n[2] Ishfaq, Haque, et al. \"Provable and Practical: Efficient Exploration in Reinforcement Learning via Langevin Monte Carlo.\" International Conference on Learning Representations, 2024.\n\n[3] Ishfaq, Haque, et al. \"Randomized exploration in reinforcement learning with general value function approximation.\" International Conference on Machine Learning. PMLR, 2021.\n\n[4] Dubey, Abhimanyu, and Alex Pentland. \"Provably efficient cooperative multi-agent reinforcement learning with function approximation.\" arXiv preprint arXiv:2103.04972 (2021).\n\n[5] Min, Yifei, et al. \"Cooperative multi-agent reinforcement learning: Asynchronous communication and linear function approximation.\" International Conference on Machine Learning. PMLR, 2023.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "3v5ivdyhWc", "reviewer": "Reviewer_kVyU", "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.", "questions": "1. Can you highlight a bit more about the technique novelty of the proposed methods?\n\n2. In Page 26, line 877, can you explain in details why the inequality holds?\n\n3. 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": "N.A.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The authors contribute some new algorithms in this cooperative learning setting, and derive their regret bounds. The paper writing is also easy to follow. The experiments results are provided to verify the performance of algorithms.", "weaknesses": "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.\n\n2. The comparison with previous work is not precise and misleading:\n\n    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.\n\n3. 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).\n\n    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. \n\n4. 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.\n\n\n[1] Zanette et al., Learning Near Optimal Policies with Low Inherent Bellman Error", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable time and providing positive feedback on our work. We hope our response will fully address all of your points. \n\n### Q1. Discussion on multi-task RL and multi-agent RL \n\nOur work focuses on parallel MDPs, which have been categorized as multi-agent RL in the literature [1, 2, 4, 5]. While there are similarities with multi-task RL, especially in our extension to handle heterogeneity [6], our primary goal is to accelerate learning of individual MDPs by leveraging shared transition structures. This differs from multi-task RL, which involves solving multiple distinct tasks [7-9]. We will include relevant multi-task RL literature in the final version.\n\n---\n### Q2.  The comparison with previous work [3]\n\nThank you for your suggestion! We would like to make our statement more accurate and concise. We intended to mean in line 221 that our result matches the existing best single-agent result using randomized exploration [10, 11]. We will polish our writing in our revision. [3] proposed ELEANOR, an optimistic generalization of the popular LSVI algorithm and derived the regret bound $\\widetilde{O}(d H^2 \\sqrt{K})$ under the same setting of ours. We will also add the comparison of [3] in Table 1 in the final version.\n\n---\n### Q3. Trade off between regret and communication complexity\n\nWe first individually derive the regret bound (Theorem 4.2 and 4.3) and communication complexity with respect to $\\gamma$. Then we choose a proper $\\gamma=O(K/dM)$ to match the regret with other multi-agent results [1, 2]. Then we find our communication complexity matches the result of [2] and is better than [1]. We also further discuss the differences between synchronous and asynchronous settings in Remark 4.7.\n\n---\n### Q4. Concerns about synchronization \n\nWe would like to clarify that our synchronization framework is a general setting and one main contribution of this work is to present how to incorporate random exploration strategies into this framework from both theoretical and experimental perspectives. Specifically, the synchronization condition in (3.3) contributes to the theoretical derivation of both regret and communication complexity. On the other hand, we mention in line 142 that we investigate three types of synchronization rules in the experiments. Although the synchronization rule from (3.3) still results in the most competitive performance, we show that other synchronization rules’ performance is also closer. We consider incorporating domain knowledge with criteria for specific tasks to constrain the synchronization in future work. \n\n---\n### Q5. Generalization beyond linear setting & Q6. About technical novelty of the proposed method \n\nPlease refer to our **General Response** for all reviewers due to space limit.\n\n---\n### Q7. Proof explanation for the inequality in page 26, line 877\n\nThis inequality holds because: 1. $(I+A_i)^{-1} \\preccurlyeq \\frac{2}{3} I$ (directly obtain from (F.2)) 2. we have set $\\beta_{m, i}=\\beta_K$ for all $i \\in[k]$ and $m \\in \\mathcal{M}$ 3. $A_i^{2 J_i}(\\Lambda_{m, h}^i)^{-1} = A_i^{J_i}(\\Lambda_{m, h}^i)^{-1} A_i^{J_i}$ because $A_i=I-2 \\eta_{m, i} \\Lambda^i_{m, h}$.\n\n---\n### Q8. Explanation for the definition in page 28, line 891\n\nFirst, we would like to emphasize again that to simplify the notations in the proof for CoopTS-LMC, we eliminate the index $n$ (the multi-sampling number) before Lemma E.7 because the previous lemmas have nothing to do with multi-sampling. This has been mentioned at the beginning of the proof (line 779). \nSo $w_{m, h}^{1,0}$ is $w_{m, h}^{k, j, n}$ with $k=1,j=0$ and eliminated $n$, here we initialize $w^{1,0}_{m, h}=0$.\n\nMoreover, $\\widehat{w}^1_{m, h}, \\Lambda^1_{m, h}, b^1_{m, h}$ is defined in line 640-642 with $k=1$.\n\n---\nWe hope we have addressed all of your questions. If you have any further questions, we would be happy to answer them and if you don’t, would you kindly consider increasing your score?\n\n\n### References:\n\n[1] Dubey, Abhimanyu, and Alex Pentland. \"Provably efficient cooperative multi-agent reinforcement learning with function approximation.\" arXiv preprint arXiv:2103.04972 (2021).\n\n[2] Min, Yifei, et al. \"Cooperative multi-agent reinforcement learning: Asynchronous communication and linear function approximation.\" International Conference on Machine Learning. PMLR, 2023.\n\n[3] Zanette, Andrea, et al. \"Learning near optimal policies with low inherent bellman error.\" International Conference on Machine Learning. PMLR, 2020.\n\n[4] Lidard, Justin, et al. “Provably Efficient Multi-Agent Reinforcement Learning with Fully Decentralized Communication.” IEEE American Control Conference (ACC), 2022. \n\n[5] Cisneros-Velarde, Pedro, et al. “One Policy is Enough: Parallel Exploration with a Single Policy is Near-Optimal for Reward-Free Reinforcement Learning.” International Conference on Artificial Intelligence and Statistics, 2023 \n\n[6] Zhang, Chicheng, et al. “Provably efficient multi-task reinforcement learning with model transfer.” Advances in Neural Information Processing Systems 34 (2021)\n\n[7] Shi, Chengshuai, et al. “Provably Efficient Offline Reinforcement Learning with Perturbed Data Sources.” International Conference on Machine Learning. PMLR, 2023.\n\n[8] Sodhani, Shagun, et al. \"Multi-Task Reinforcement Learning with Context-based Representations.\" Proceedings of the 38th International Conference on Machine\nLearning, 2021.\n\n[9] Amani, Sanae, et al . “Scaling Distributed Multi-task Reinforcement Learning with Experience Sharing.” arXiv preprint arXiv:2307.05834 (2023).\n\n[10] Ishfaq, Haque, et al. \"Provable and Practical: Efficient Exploration in Reinforcement Learning via Langevin Monte Carlo.\" International Conference on Learning Representations, 2024.\n\n[11] Ishfaq, Haque, et al. \"Randomized exploration in reinforcement learning with general value function approximation.\" International Conference on Machine Learning. PMLR, 2021.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "nRqlDrKpqD", "reviewer": "Reviewer_WAEL", "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.", "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.\n\nThis 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": "Yes.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "**Significance**: \n\n**1.** The paper proposed the first meaningful theoretical result for randomized exploration in multi-agent cooperative RL. \n\n**2.** The algorithms are not only theoretically meaningful, but also easy to implement and has various advantages such as computational efficiency and avoidance of sampling bias.\n\n**Quality**: this paper is high-quality. \n\n**1.** The theory part of this paper is very solid.\nFirst a unified framework is introduced which has wide applicability and can incorporate various specific settings. Then detailed application to linear MDP with theoretical guarantees is given. The paper further considers the misspecified setting where the transition kernel is slightly misspecified in a certain way, which can be common in practice. This helps extend the applicability of the proposed method.\n\n**2.** The experimental result of this paper is extensive. Results on both video games and realistic energy control are provided.\n\n**Clearity**: This paper is clearly written.  \n\n**1.** The theory of this paper is very clear, with the help of well-chosen terms and notations, unambiguous definitions and clear description of theorems. \n\n**2.** A detailed table comparing all necessary related works is provided, helping readers quickly grasp the pros and cons of the proposed methods.\n\n**3.** In section 3.1 and 3.2, a thorough description of the interpretation behind the PHE and LMC strategy is given. The rationale behind the synchronization rules is explained. \n\n**4.** For all the experiments in section 5, the necessary implementation detail is given.", "weaknesses": "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable time and providing positive feedback on our work. We hope our response addresses your question.\n\n---\n### Q1. Extension of the algorithm beyond linear MDP setting\n\nEmpirically, we would like to clarify that our algorithm is designed for general function approximation. For general MDPs, we could simply utilize a more powerful and expressive function class to approximate the value function and then directly apply our proposed algorithms since their update rules ((3.5) and (3.7) in the paper) can work with any function classes. This is in contrast with UCB and vanilla TS based algorithms [1, 2] which need to precisely compute the exploration bonus term based on the linear structure of the reward or value function. \n\nTheoretically, when the transition is a linear MDP, it is equivalent to assuming the value function is linear and thus we can apply linear function classes with our algorithms. However, if we want to extend the theoretical results to richer MDPs beyond linear MDPs, it would require us to be able to analyze the convergence of the randomized strategies to the true posterior distribution which might be non-log-concave. We suspect this could be done by following some rigorous analyses in the approximate sampling literature for non-log-concave distributions [3]. Nevertheless, these results tend to have exponential dependency on the dimension or depend on specific assumptions on the properties of the posterior distributions, which could complicate the analysis and make the regret analysis vacuous without developing dedicated techniques. Thus we leave these interesting and challenging topics for future study. \n\n---\nWe hope we have addressed all of your questions/concerns. If you have any further questions, we would be more than happy to answer them.\n\n\n### References:\n\n[1] Chu, Wei, et al. \"Contextual bandits with linear payoff functions.\" Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics. JMLR Workshop and Conference Proceedings, 2011.\n\n[2] Jin, Chi, et al. \"Provably efficient reinforcement learning with linear function approximation.\" Conference on learning theory. PMLR, 2020.\n\n[3] Dalalyan, Arnak S. \"Theoretical guarantees for approximate sampling from smooth and log-concave densities.\" Journal of the Royal Statistical Society Series B: Statistical Methodology 79.3 (2017): 651-676.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
## General response

We would like to thank all reviewers for your insightful and detailed reviews and comments. We have addressed your comments and revised the manuscript accordingly. In the following, we would like to provide general responses to several common questions raised by reviewers.

---
### Q1. Generalization beyond linear setting

Empirically, we would like to clarify that our algorithm is designed for general function approximation. For general MDPs, we could simply utilize a more powerful and expressive function class to approximate the value function and then directly apply our proposed algorithms since their update rules ((3.5) and (3.7) in the paper) can work with any function classes. This is in contrast with UCB and vanilla TS based algorithms [6] which need to precisely compute the exploration bonus term based on the linear structure of the reward or value function. 

Theoretically, when the transition is a linear MDP, it is equivalent to assuming the value function is linear and thus we can apply linear function classes with our algorithms. However, if we want to extend the theoretical results to richer MDPs beyond linear MDPs, it would require us to be able to analyze the convergence of the randomized strategies to the true posterior distribution which might be non-log-concave. We suspect this could be done by following some rigorous analyses in the approximate sampling literature for non-log-concave distributions [5]. Nevertheless, these results tend to have exponential dependency on the dimension or depend on specific assumptions on the properties of the posterior distributions, which could complicate the analysis and make the regret analysis vacuous without developing dedicated techniques. Thus we leave these interesting and challenging topics for future study. 


---
### Q2. About technical novelty of the proposed method 

1. Our work is the first study on provably efficient randomized exploration in cooperative multi-agent RL, with both theory and empirical evidence. No prior work has implemented provable randomized exploration in this multi-agent setting, there have been even no experiments involving UCB exploration in the multi-agent setting in previous studies.

2. 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. Through empirical evaluation, we demonstrate that our proposed framework with synchronous communication scheme has a better performance and also compare different synchronization conditions (which we showed in Figure 6 and discuss in Appendix J). Our experiments also support that our randomized exploration strategies outperform existing deep $Q$ network (DQN)-based baselines. By proposing Algorithm 4, we also show that our random exploration strategies in cooperative MARL can be adapted to the existing federated RL framework when data transitions are not shared. We believe that our empirical results have enough contributions and provide solid support for relevant theoretical analysis.

3. In the linear Parallel MDPs setting, we give the first theoretical result for randomized exploration. Both our regret upper bound and communication complexity match the currently best results of UCB-type of algorithms in the same setting. Moreover, we extend our theoretical analysis to the misspecified setting where the transition and the reward functions are heterogeneous across different MDPs, which is more general than the previous work (we discuss in Remark D.2 in Appendix D). In Remark D.6, we also discuss that CoopTS-PHE has better performance tolerance than CoopTS-LMC  for the misspecified setting, which is aligned with our experimental results in Figure 1(b).

4. In the theoretical analysis, we also fixed a non-negligible error in the regret decomposition that previous work ignored (we discuss this in Remark 4.5). To be specific, in proofs for both CoopTS-LMC and CoopTS-PHE we use a new $\varepsilon$-covering technique to prove that the optimism lemma holds for all $(s, a) \in \mathcal{S} \times \mathcal{A}$ instead of just the state-action pairs encountered by the algorithm, which is essential for the regret analysis. This was ignored by previous work [1] and its follow-up work [2] that use the same regret decomposition technique. Furthermore, the multi-agent setting and the communications from synchronization in our algorithms also increase the challenges in our analysis compared to randomized exploration in the single-agent setting [2, 3]. In Appendix C, we also provide a refined analysis of communication complexity and get the currently best regret bound. This is an improvement compared with previous work [4].

### References:

[1] Cai, Qi, et al. "Provably efficient exploration in policy optimization." International Conference on Machine Learning. PMLR, 2020.

[2] Ishfaq, Haque, et al. "Provable and Practical: Efficient Exploration in Reinforcement Learning via Langevin Monte Carlo." International Conference on Learning Representations, 2024.

[3] Ishfaq, Haque, et al. "Randomized exploration in reinforcement learning with general value function approximation." International Conference on Machine Learning. PMLR, 2021.

[4] Dubey, Abhimanyu, and Alex Pentland. "Provably efficient cooperative multi-agent reinforcement learning with function approximation." arXiv preprint arXiv:2103.04972 (2021).

[5] Dalalyan, Arnak S. "Theoretical guarantees for approximate sampling from smooth and log-concave densities." Journal of the Royal Statistical Society Series B: Statistical Methodology 79.3 (2017): 651-676.

[6] Jin, Chi, et al. "Provably efficient reinforcement learning with linear function approximation." Conference on learning theory. PMLR, 2020.

Meta-review: 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.
Decision: Accept (poster)