Best Possible Q-Learning

The observation of the global state can be a strong assumption.

To the best of our knowledge, BQL is the first method to guarantee the convergence and optimality on the global state in decentralized MARL, other baselines even cannot guarantee the optimality on the global state.

The uniqueness of the joint optimal policy can also be strong.

Whether the optimality can be guaranteed with multiple optimal policies in decentralized MARL is still an open problem. To the best of our knowledge, no method can theoretically solve this problem in fully decentralized settings. In Appendix D, we have discussed how to deal with the case with multiple optimal policies.

How is eq (4) obtained?

Eq(3) does not require $a = \pi^*(s)$, but describes the optimal value given any $a$. (4) is from taking $\max_{a_{-i}}$ on both sides of (3) so it does not require $a_i = a_i^*$.

In the case of there exists only one optimal policy, why is it deterministic?

Puterman's book says that there exists at least one deterministic optimal policy in an MDP, so if there exists only one optimal policy, this policy must be deterministic.

In the proof of Lemma 4, the convergence is based on the fact that the optimal kernel is chosen during updating. What if the kernel is never chosen?

In tabular cases, it is easy to sample all kernels. Any kernel can be chosen so the optimal kernel will be chosen.

When only deterministic policies are considered, the set of all possible kernels is finite, making Q3 a bit reasonable. But what if random policies are also considered?

There exists at least one deterministic optimal policy in an MDP, so we only need to consider the deterministic policies. Especially when there is only a unique optimal policy, stochastic policies must not be optimal.

Dear Reviewer bFNq,

Have we addressed your concerns? If you have any other questions, please let us know.

Sincerely,

Authors

My major concern is the lack of quantitative results, which raises questions about the impact and significance of the theoretical findings.

(1) The convergence presented in the paper is asymptotic, based on the fact that improvement only occurs when the best kernel is selected. However, how likely is this to happen? When the state/action space is large, the probability of selecting the best kernel becomes smaller, potentially leading to significantly slower convergence rates. Sure the algorithm will converge, but is it linearly fast? Or could the rate become exponentially slow as $S,A$ scale? The lack of a quantitative characterization makes the impact of this result unclear. The asymptotic convergence is expected and such a result alone is not informative.

(2) What is the total computational complexity of the simplified operator until it converge to the optimal policy? Intuitively, the average number of ineffective updates (i.e., when the best kernel is not selected) appears to match the total number of kernels. If this is the case, the computational cost is not reduced compared to the best possible operator (in expectation sense), making the claim of reduced cost unconvincing. A quantitative characterization would make these discussions much clearer.

For the current version, the claims are not fully supported by the theoretical results. Furthermore, the proof offers limited insights or novelty, and it provides little practical guidance (e.g., expected computational costs of the algorithm implementations). Therefore, I feel the paper is not yet ready for publication.

We agree the complexity of BQL is high, but that is because the complexity of fully decentralized MARL is high (https://arxiv.org/pdf/1301.3836). To the best of our knowledge, no other algorithm shows lower complexity or faster convergence than BQL in this problem.

Why do you think the proof offers limited insights or novelty? The proof shows that BQL is the first algorithm to guarantee convergence and optimality in fully decentralized MARL. Is it not novel enough? Why do you think the proof provides little practical guidance? The derived algorithm from the proof achieves significant performance gain in experiments.

Do you really think the complexity or convergence rate provide any practical guidance? Think about the successful RL applications, AlphaGo and ChatGPT, which one is related to the analysis of complexity or convergence rate? In large-language model, the space of state-action pair is incredibly large, the complexity analysis is ridiculous in front of it. Excessive focus on complexity analysis is a significant obstacle to the practical application of RL, and a waste of life.

Q2

The result is a property of any MDP, for both single agent and multi agents. When we talk about the optimal policy in MARL, we mean the optimal joint policy. There exists at least one deterministic optimal joint policy in a multi-agent MDP. Your understanding of joint policy is correct, which means the global action $<a_1,a_2,....,a_N>$.

Q3

You might have confused theory with practice. In Lemma 4, we talk about theory. In theoretical proof, we should go through all kernels to guarantee the convergence and optimality, just like that Q-learning assumes going through all state-action pairs. Since the analysis of Q-learning requires countable state-action pairs, the kernels will not be infinite in theoretical proof with deterministic policy. In the case of infinite many kernels exist, it is beyond the scope of theoretical proof, and we only talk about practice. The experimental results can evaluate the performance of BQL in that case.

Dear reviewer bFNq,

We feel that you are requiring us to thoroughly solve the problem of decentralized MARL. But the aim of this paper is to obtain a practical algorithm from the analysis of convergence and optimality. Complexity analysis usually stands alone as a separate paper. And we have to argue that complexity analysis is not a reason for rejecting an ICLR paper, because ICLR is not a conference for mathematics. You mentioned that we focus on a simplified setting with only one optimal policy, however, whether the optimality can be guaranteed with multiple optimal policies in decentralized MARL is still an open problem. And the study on this problem called coordination also usually stands alone as a separate paper. You mentioned the experiments are limited, but you also said that you do appreciate the experiment part in the main review. You mentioned that the problem of MARL is definitely important in the main review, but have you ever thought about the reason why the previous methods on this important problem are so limited? We believe that when we evaluating a research paper, we should compare it with the previous methods, instead of requiring it to solve all aspects in a research field.

Please check our response to Reviewer sXth. The stochastic algorithm is proposed for neural network implementation not for complexity. The best operator cannot be written as a loss function for a neural network because each agent has to compute the expected values of all possible transition probabilities, so the stochastic algorithm is needed.

It seems that you deeply believe the complexity is necessary to RL application, so do you know the complexity of PPO in general cases?

You said BQL is poor in complexity analysis, scalability, experiments, and easier setting. However, the previous methods in decentralized MARL even cannot guarantee convergence and optimality, so the complexity cannot be discussed. And the previous methods show worse scalability, easier settings (see related work), and more limited experimental results than BQL. After you read these papers, do you think the previous methods should also be rejected or this research field should be vanished? Frankly, this research field has already been vanished.

Surely the claim of global optimality in line 62 is restricted to tabular cases, right? Please clarify the setting in which this claim is valid.

In the Q-learning field, all discussions of convergence and optimality of are based on tabular cases since the convergence of Q-learning cannot be guaranteed in neural network approximation, as shown in (https://arxiv.org/pdf/1903.08894).

Why can’t we treat all agents as one “super agent” whose action space is the product space of the individual agents? At the very least, the authors should provide a reference for the statement of non-convergence on line 87

In fully decentralized MARL, each agent does not know other agents' action space, so the action space cannot be the product space of the individual agents. The non-convergence of IQL (line 87) is common knowledge and is discussed in all related work listed.

I do not follow the step from line 142 to line 144. Is it generally true that max_x f(x) - max_x g(x) \ge f(x’) - g(x’) for a generic x’ (here, x’ is analogous to a_i^{‘*})? I can certainly find counterexamples in general, so what is special about this case which admits this inequality?

$\max_x f(x) - \max_x g(x) \ge f(x’) - g(x’)$ where $g(x’) = \max_x g(x)$. Since $\max_x f(x)$ is the max of $f(x)$, $\max_x f(x) \ge any f(x’)$. How to build the counterexamples?

I am not clear on why we need to “explore” all state/action pairs with a deterministic policy (looking at line 236). Can’t we just enumerate them in a tabular problem? Please explain why the exploration is needed and enumeration does not suffice.

Of course, we can enumerate them. Enumeration is a special case of exploration. Our algorithm shows how to explore them if enumeration is not allowed.

Dear reviewer HS25,

Since we haven't received your response, can we assume that you think there is no fatal flaw in BQL?

Scalability

First, we have to argue that the complexity converging the optimum in fully decentralized MARL is high. The complexity exponentially grows as the number of agents increases, so any algorithm for fully decentralized MARL must have exponential complexity. Second, in neural network implementation, we only maintain one replay buffer for each agent, without explicitly storing $P(\cdot|s, a_i a_{-i})$ or searching over all possible $\pi_{-i}$. So the sample collection of BQL is consistent with other baselines. Third, in Figure 3(d), BQL can achieve significant performance improvement when the agent number is large (17 agents), which shows the scalability of BQL is better than other baselines. Last, the aim of (7) is not to reduce the search time, but for the convenience of neural network implementation. The operator (6) has the same complexity as the simplified version (7,8), but the operator (6) cannot be written as a loss function for a neural network because each agent has to compute the expected values of all possible transition probabilities.

A closely related work [1] deals with theoretical convergence of independent Q-learning. Please provide comparison with the work in sense that how the setting is different, and pros and cons.

Sorry, but the citation [1] seems to be missed.

In Lemma 1, why do we need the condition of existence of only one optimal policy?

Without this condition, BQL can still converge to the optimal value but does not know how to select the optimal joint action. Look at the matrix game in Figure 11, there are two optimal policies (1,2) and (2,1). For each agent, actions 1 and 2 have the same highest optimal learned value. If each agent arbitrarily selects one of the optimal independent actions, the selected joint action might not be optimal (policy (1,1)). We have discussed the problem of multiple optimal policies in Appendix D.

In Section 2.4, $S^m_i$ has not been explained previously.

We have claimed that $S^m_i$ is a subset of states randomly selected by agent $i$ at the epoch $m$ at line 238.

Thank you for reviewing our paper. We will carefully address your questions.

It can be restrictive to assume there is only a unique optimal policy. How does the proposed algorithm perform when there are multiple optimal policies?

In Appendix D, we have discussed how to deal with the case with multiple optimal policies and provided a one-stage matrix game in Figure 11. BQL can select coordinated actions, though the value gap between the optimal policy and suboptimal policy is so small.

Can the authors provide explicit theorems and proofs for the convergence and optimality of BQL for both the tabular case and the neural network case?

We have proven the convergence and optimality of tabular case. The convergence of Q-learning cannot be guaranteed in function approximation methods, e.g., DQN with a neural network, as shown in (https://arxiv.org/pdf/1903.08894).