Randomized Exploration in Cooperative Multi-Agent Reinforcement Learning

Thank you for your valuable time and providing positive feedback on our work. We hope our response addresses your question.

Q1. Extension of the algorithm beyond linear MDP 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 [1, 2] 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 [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.

We hope we have addressed all of your questions/concerns. If you have any further questions, we would be more than happy to answer them.

References:

[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.

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

[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.

Thank you for your valuable time and providing positive feedback on our work. We hope our response will fully address all of your points.

Q1. Discussion on multi-task RL and multi-agent RL

Our 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.

Q2. The comparison with previous work [3]

Thank 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.

Q3. Trade off between regret and communication complexity

We 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.

Q4. Concerns about synchronization

We 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.

Q5. Generalization beyond linear setting & Q6. About technical novelty of the proposed method

Please refer to our General Response for all reviewers due to space limit.

Q7. Proof explanation for the inequality in page 26, line 877

This 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}$.

Q8. Explanation for the definition in page 28, line 891

First, 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). So $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$.

Moreover, $\widehat{w}^1_{m, h}, \Lambda^1_{m, h}, b^1_{m, h}$ is defined in line 640-642 with $k=1$.

We 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?

References:

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

[2] Min, Yifei, et al. "Cooperative multi-agent reinforcement learning: Asynchronous communication and linear function approximation." International Conference on Machine Learning. PMLR, 2023.

[3] Zanette, Andrea, et al. "Learning near optimal policies with low inherent bellman error." International Conference on Machine Learning. PMLR, 2020.

[4] Lidard, Justin, et al. “Provably Efficient Multi-Agent Reinforcement Learning with Fully Decentralized Communication.” IEEE American Control Conference (ACC), 2022.

[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

[6] Zhang, Chicheng, et al. “Provably efficient multi-task reinforcement learning with model transfer.” Advances in Neural Information Processing Systems 34 (2021)

[7] Shi, Chengshuai, et al. “Provably Efficient Offline Reinforcement Learning with Perturbed Data Sources.” International Conference on Machine Learning. PMLR, 2023.

[8] Sodhani, Shagun, et al. "Multi-Task Reinforcement Learning with Context-based Representations." Proceedings of the 38th International Conference on Machine Learning, 2021.

[9] Amani, Sanae, et al . “Scaling Distributed Multi-task Reinforcement Learning with Experience Sharing.” arXiv preprint arXiv:2307.05834 (2023).

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

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

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.

Q1. Detailed explanation about challenges in theoretical analysis.

We explain the specific improvements we made in our theoretical analysis here.

1. 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.

2. 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].

3. 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.

4. 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.

We hope these illustrations could show our contributions on the theoretical analysis to you more clearly.

Q2. The tradeoff between using perturbed history exploration and Langevin Monte Carlo exploration

We discuss the comparisons between PHE and LMC in the following three aspects: algorithm design, theoretical results and experiments.

1. 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.

2. 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).

3. 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.

We 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?

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] Min, Yifei, et al. "Cooperative multi-agent reinforcement learning: Asynchronous communication and linear function approximation." International Conference on Machine Learning. PMLR, 2023.

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.

Q1. Explanation for the configuration of the contenders

All 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.

It 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.

We 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.

Q2. Explanation of the experimental results

First, 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.

In 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.

Q3. Practical setting of parameter $\gamma$

We 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.

We 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?