A Finite-Time Analysis of Distributed Q-Learning

Authors: Han-Dong Lim, Donghwan Lee
Primary area: reinforcement learning
Keywords: reinforcement learning, multi-agent, distributed learning, q-learning

Abstract:
Multi-agent reinforcement learning (MARL) has witnessed a remarkable surge in interest, fueled by the empirical success achieved in applications of single-agent reinforcement learning (RL). In this study, we consider a distributed Q-learning scenario, wherein a number of agents cooperatively solve a sequential decision making problem without access to the central reward function which is an average of the local rewards. In particular, we study finite-time analysis of a distributed Q-learning algorithm, and provide a new sample complexity result of $\tilde{\mathcal{O}}\left( \max\left\\\{  \frac{1}{\epsilon^2}\frac{t_{\text{mix}}}{(1-\gamma)^6 d_{\min}^4 }  ,\frac{1}{\epsilon}\frac{\sqrt{|\mathcal{S}||\mathcal{A}|}}{(1-\sigma_2(\boldsymbol{W}))(1-\gamma)^4 d_{\min}^3}  \right\\\} \right)$ under tabular lookup setting for Markovian observation model.

Decision: reject
Reviewer scores: 5, 5, 5, 5

Reviews and discussion:
<thread>
creation date:
1729027195010

thread_type:
official_review

<thread_object>
creator: reviewer_gtxi

<content>
summary:
This paper studies distributed Q learning, where the agent communicate through a graph. The finite-time convergence under both iid and Markovian samples are studied.

strengths:
The problem of distributed Q learning is important and interesting. The convergence results also are SOTA.

weaknesses:
1. Although the notations are defined mathematically, it can be more clear with additional explaniation. For example, in lines 225-227, it would be godd to explan what $\delta, \Delta$ are. 
2. The introduction of the switched system looks odd to me. If it is only for proof technique, might should introduced in the proof part. 
3. The proof technique is standard by following single agent Q-learning, and analysis for multi agent system is also studied. For example, a quick search results in a study [1], where robust multi-agent Q learning is studing. The non-robust is a special case with $R=0$. Hence it make me feel the novelty here is incremental. 
4. Analysis of Markovian vs iid is also not new. 



[1] Wang, Yudan, et al. "Data-driven robust multi-agent reinforcement learning." 2022 IEEE 32nd International Workshop on Machine Learning for Signal Processing (MLSP). IEEE, 2022.

questions:
What is the novelty compared to existing works?

Can you address the weakness part?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730312461053

thread_type:
official_review

<thread_object>
creator: reviewer_zsxf

<content>
summary:
This paper provides the first sample complexity bounds for distributed Q-learning scenario in tabular setting. It is a topic of increasing interest and importance given the empirical success achieved in applications of single-agent reinforcement learning.

strengths:
It is the first paper that provides the sample complexity bounds for tabular distributed Q-learning without relying on any strong assumptions.

weaknesses:
1.	In Corollary 3.8 and Corollary 4.2, the restrictions regarding the step size alpha are missing. These restrictions are used in the proof but are not mentioned in these two corollaries. Additionally, the restriction on $\alpha$ in line 1194 of the proof for Corollary 3.8 should be proportional to $\epsilon$ rather than its reciprocal.
2.	Instead of comparing the dependencies on graph structure, I recommend a comparison of the entire sample complexity bounds with the other two baselines.
3.	The experiment design is not very clear. For example, how are the transition functions and rewards generated? What is the number of agents? Why do you choose to compare your method with QD-learning? Moreover, $S = 2$ seems small and it is better to try some larger-scale experiments.
4.	There are some undefined notations and typos in the paper:
- The agent collection $V$ and the discount factor $\gamma$ are not defined at the beginning of the preliminary section.
- In the Bellman equation, $s$ in the maximum term should be $s’$.
- In line 220, the dimensions of the two matrices are incorrect.
- In line 270, $R_{max}$ is not defined.
- In line 436, it should be noted that $\rho < 1$.
- In line 1006, the content exceeds the page limitation.

questions:
Your multi-agent MDP setting differs from the conventional MAMDP model, as you assume the agents share a common trajectory. Is this setting applicable in real-world scenarios, and are there other papers employing a similar setting?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730464414706

thread_type:
official_review

<thread_object>
creator: reviewer_4vwu

<content>
summary:
In this paper, the authors present a finite-time analysis of distributed Q-Learning, where the agents need to cooperatively maximize an average of local rewards. Specifically, the agents do not have access to any global information and can only communicate with neighboring agents during the learning process. They show that a distributed Q-learning algorithm has a $\tilde{\mathcal{O}}\left(\max \left\\{\frac{1}{\epsilon^2} \frac{t_{\text{mix}}}{(1-\gamma)^6 d_{\min }^4}, \frac{1}{\epsilon} \frac{\sqrt{|\mathcal{S}||\mathcal{A}|}}{(1-\sigma_2(\mathbf{W}))(1-\gamma)^4 d_{\text {min }}^3}\right\\}\right)$ sample complexity bound.

strengths:
* The paper is the first to give sample complexity bounds for the distributed Q-learning algorithm without restrictive assumptions.

* The results are technically sound.

weaknesses:
* The technical contribution of this paper is unclear. It appears that the results are obtained by accommodating the analysis technique in [1] to the distributed setting. I suggest the authors elaborate on their technical contribution in the intro.

* The sample complexity bounds are of the order $\tilde{\mathcal{O}}\left(\max \left\\{\frac{t_{\text {mix }}}{\epsilon^2} \frac{|\mathcal{S}|^2 |\mathcal{A}|^{2}}{(1-\gamma)^6}, \frac{1}{\epsilon} \frac{|\mathcal{S}|^{\frac{5}{2}}  |\mathcal{A}|^{\frac{5}{2}}}{(1-\gamma)^4\left(1-\sigma_2(\mathbf{W})\right)}\right\\}\right)$. This bound is significantly larger compared to existing results in single-agent and federated RL. The authors should discuss whether this large bound arises from a loose analysis or the inherent nature of the problem setting. It may also help to compare the results with results on federated RL.

* The main body of the paper is written in an immense technical style. I suggest the authors try to make the proof outlines more accessible and discuss the implications of their theoretical results.


Since I am not very familiar with the field of MARL, I choose to assign a low confidence score to my evaluation.

[1] D. Lee and N. He. A unified switching system perspective and convergence analysis of q-learning algorithms. Advances in Neural Information Processing Systems, 33:15556–15567, 2020.

questions:
* What would happen if we choose matrix $W$ to let all agents be able to communicate with each other? Would the problem setting degenerate into a centralized case? Is a better theoretical guarantee possible?

* Except for the case in Appendix B, are there any other choices of $W$ in common examples of practical applications? What is the scale of $\sigma_2(W)$, respectively?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730704302559

thread_type:
official_review

<thread_object>
creator: reviewer_3rf8

<content>
summary:
This work explores multi-agent reinforcement learning, where multiple agents collaboratively learn their individual policies in order to maximize the total cumulative rewards of all agents. They introduce a distributed Q-learning algorithm in which each agent updates its Q-estimates by aggregating the Q-values of its neighbors, weighted by a specified weight matrix. Furthermore, they provide a finite-time convergence analysis of the proposed algorithm in a tabular setting under mild assumptions.

strengths:
1. The paper presents a finite-time convergence analysis under relaxed conditions.

weaknesses:
1. The sample complexity presented is significantly distant from the tightest bound for the single-agent case in \cite{1}. In particular, considering that \( d_{\text{min}} \le \frac{1}{SA} \), the dependence on \( \frac{1}{(d_{\text{min}})^3} \) and \( \frac{1}{(d_{\text{min}})^4} \) seems critical. It remains uncertain whether the reported sample complexity adequately reflects the impact of key parameters on the learning process.
2. While the analysis is presented under milder conditions compared to the baselines, it is conducted in a tabular setting, which is simpler than those of the baselines. Therefore, it remains unclear whether the relaxation of assumptions in the simpler setting shows sufficient technical novelty.
3. It lacks a comparison with other decentralized RL algorithms, such as [2], which could provide better insights into the unique dependencies observed in decentralized scenarios and the unique challenges present in multi-agent settings. While this paper addresses a more general scenario where agents' actions can influence the rewards of others, it appears that this setting can encompass decentralized reinforcement learning with environmental heterogeneity, where agents aim to maximize average rewards, which seems more relevant to this work than the single-agent case.

[1] Li, C. Cai, Y. Chen, Y. Wei, and Y. Chi. Is q-learning minimax optimal? a tight sample complexity analysis. Operations Research, 72(1):222–236, 2024. \
[2] Tong Yang, Shicong Cen, Yuting Wei, Yuxin Chen, and Yuejie Chi. Federated natural policy gradient methods for multi-task reinforcement learning. arXiv preprint arXiv:2311.00201, 2023. \

questions:
1. I wonder if  \frac{1}{(d_{\text{min}})^4} also appeared in the sample complexity bound in previous works [3,4].
2. Could you provide intuitions or simple examples that explain what enables the relaxation of the assumptions? Additionally, I am curious whether this relaxation is specific to the tabular setting.

[3] P. Heredia, H. Ghadialy, and S. Mou. Finite-sample analysis of distributed q-learning for multi-agent networks. In 2020 American Control Conference (ACC), pages 3511–3516. IEEE, 2020. \
[4] Finite-time convergence rates of decentralized stochastic approximation with applications in multi-agent and multi-task learning.
</content>
</thread_object>

</thread>
<thread>
creation date:
1731928537895

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
General response (1/2)

comment:
We would like to thank all the reviewers for their valuable feedback, as well as for the time and effort they dedicated to reviewing our paper. In response to their comments, we have made several revisions to the manuscript, with the changes highlighted in $\textcolor{red}{red}$. Below, we provide a summary of the modifications in the revised version:


**G1. Comparison with Wang et al.:**

Reviewer Gtxi pointed out a closely related work by Wang et al., which we have missed in the initial submission. The work proposed a distributed Q-learning algorithm in the tabular setting, which is motivated from the adapt-then-combine algorithm [2], whereas our algorithm considers combine-and-adapt scheme in the distributed optimization literature. The combine-and-adapt scheme first aggregates information from the neighbours and then executes update while in the adapt-and-combine scheme, the update occurs before aggregation. The work presents a sharper bound on the sample complexity $\frac{1}{(1-\gamma)^5d_{\min}\epsilon^2}$ compared to ours, $\frac{1}{(1-\gamma)^6d_{\min}^4\epsilon^2}$. However, we would like to note several differences and advantages of the proposed analysis as follows:**1)** In Wang et al., the finite-time bound only holds for restricted range of $\epsilon$, i.e., $\epsilon\in \left[0,\frac{1}{1-\gamma} \right)$, while our result does not have such a restriction.**2)** More importantly, the algorithm proposed by Wang et al. requires two steps for a single update, whereas in our paper, we focus on a one-step algorithm that is algorithmically simpler and more efficient. Specifically, we analyze the traditional and widely adopted QD-learning algorithm proposed in [4], for which a finite-time error analysis for the original form has been lacking in the literature. Additionally, we enhance the efficiency of QD-learning by employing a constant step-size, as opposed to the two-time-scale decaying step-size used in traditional QD-learning. This modification can significantly improve the convergence speed empirically.

**G2. Sub-optimal sample complexity:**

As we have mentioned as the limitation of our work, the dependency on $d_{\min}$ or $\frac{1}{1-\gamma}$ is sub-optimal compared to the single-agent case. While we acknowledge there is a room for improvement in our finite-time bound, even in the case of single-agent Q-learning, it took over 20 years of research—from [2] to [1]—to refine the sample complexity. Therefore, we believe our work represents a significant advancement in the field.
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper studies the finite-sample analysis of a type of distributed Q-learning algorithm, QD-learning, in multi-agent distributed reinforcement learning. The analyses extended the switched-system-based perspective and technique for analyzing (single-agent) Q-learning, to this multi-agent distributed case. The paper is overall well-written, with solid technical results. However, there were some concerns regarding the technical novelty, the significance and suboptimality of the bounds, and the lack of comparison with some closely related works. The clarity of some technical results/notation and the experimental results could also be improved to strengthen the paper further. I suggest the authors incorporate the feedback from this round, and prepare for other upcoming ML venues.