Best Possible Q-Learning

Lemma 2 is a crucial lemma for justifying the best possible operator. However, the second equality appears to be incorrect. Could the authors explain how it holds?

We made a correction in the revision (the colored line). The $\max _{a_i}$ should be factored out. After the correction, the proof still holds because $a^{'*}_i$ maximizes the second term but does not maximize the first term.

Is it a common setting that the reward function is only dependent on the current state and the next state (without the dependency on the action)? To me this is not commonly seen.

The setting is still general because if two joint actions lead to the same transition dynamics in the environment, the two actions should have the same effects, and we do not need to discriminate the actions. The effects of actions are reflected in the distribution of $s'$.

Imagine that we are playing a computer game. There is a certain state where the left key and the right key can lead to the same next state or the same distribution of the next state. Do we need to give the right key a higher reward to encourage the players to always select the right key?

I think (3) (where $Q(s, \boldsymbol{a})$ is equipped with some arbitrary $\boldsymbol{a}$ ) is not the expected return of the optimal joint policy.

$Q(s, \boldsymbol{a})$ means the expected return if you start in state $s$, take an arbitrary joint action $\boldsymbol{a}$, and then forever after act according to the optimal policy in the environment. (https://spinningup.openai.com/en/latest/spinningup/rl_intro.html#value-functions)

In the proof of lemma 1, I notice that there is an underlying assumption that the actions taken by other agents do not restrict the allowable actions of each agent. If this restriction is considered, does the best possible learning strategy still apply?

Yes, fully decentralized learning requires the assumption that the agents can independently make decisions. If we consider the restriction of the allowable actions of each agent, we can train the agents in a modified MDP. If the selected joint action breaks the restriction, the MDP ends and the agents receive a very large negative reward. Then the optimal joint policy in the modified MDP will be equal to the optimal joint policy in the original MDP, and agents can independently make decisions in the modified MDP.

The 3rd line under problem (6), could the authors provide exactly where is the reference in (Puterman, 1994)?

Theorem 7.1.9. of (Puterman, 1994) shows that there is at least one deterministic optimal joint policy. Therefore, when there is only one optimal joint policy, the optimal joint policy must be deterministic.

1.a.Lemma 2

Sorry for this mistake. The $\max _{a_i}$ should be factored out. We have corrected it in the revision (the colored line). After the correction, the proof still holds because $a^{'*}_i$ maximizes the second term but does not maximize the first term.

1.b.Lemma 3 and 1.c.Lemma 4:

For the second inequality of Lemma 3, we replace the expectation over transition probabilities with the infinite norm (which is larger). We will elaborate on the proofs of these two lemma in the final version with additional pages.

2. As I will detail in the following, the conditions in the convergence proof for both operators seem too strong to hold in practice. There seems to be lack of sufficient attention to how these conditions might be met, thus leading to doubts around the practical relevance of the operators.

There are four questions in this part. For the first two questions, in theoretical analysis, it is reasonable to assume that the expected values over transition probabilities are computed exactly at every step. Even Q-learning makes such assumptions. In the implementation, as DQN, we use TD-error by sampling from a non-stationary replay buffer to fit the expected values under $\tilde{P}_i$. This approximation technique is commonly adopted, so we believe your main concern is the next two questions about approximation error.

For the last two questions, the main concern is the overestimation caused by approximation error. We use Eq. 10, the weighted max update, to overcome this problem. We can choose a large $\lambda$ to mitigate overestimation. This technique is proposed in Hysteretic IQL to solve the overestimation in Distributed IQL (as discussed in Appendix B), and has been verified to be practical in decentralized learning. This solution similar to quantile regression has been used in many RL methods, e.g., implicit Q-learning. Therefore, we follow this practical solution, and experimental results show that this solution can avoid severe overestimation.

Moreover, as the discussion is ending, we finally hope you can consider the problem we solved, fully decentralized MARL, is much more challenging than CTDE setting, which means that the complexity of our operator should be high, thus we have to use some practical techniques to achieve the trade-off between efficiency and theory (the approximation error you proposed). We propose the first operator which can theoretically converge to optimal joint policy, and make it more efficient than the practical baselines which ignore the convergence and optimality. From the perspectives of theory and algorithm, we believe that BQL is really a contribution to the novel field: fully decentralized MARL. We hope you can consider this point when evaluating our work. Thank you very much!

Bests,

Authors

Thank you to the authors for their response. My apologies for the delayed reply; I hope there is still adequate time for further discussion.

I find the clarification regarding the proofs for Lemma 2-4 satisfactory, confirming my initial understanding. The issues identified appear to be presentation-related, which I believe can be rectified in subsequent revisions.

However, upon further review, I remain concerned about the theoretical framework.

Specifically, the assumption that the algorithm can exactly compute expectations with respect to transition probabilities is, in my opinion, overly restrictive and a significant limitation of the proposed method.

For instance, both the best possible operator (Eq. 6) and the simplified operator (Eq. 7) require exact computation of expectations at each Q-function update. And their convergence proofs rely on such computations.

The authors claimed that “it is reasonable to assume that the expected values over transition probabilities are computed exactly at every step”, and drew parallels with Q-learning, stating “Q-learning makes such assumptions”. I must respectfully disagree. The update rule of Q-learning does not entail such an expectation calculation. Moreover, the majority of convergence proofs in the Q-learning literature [1-4] utilize results from stochastic approximation without presuming the agent’s access to true transition probabilities.

This assumption raises a fundamental question: If the algorithm indeed has access to true transition probabilities, as implied in Equations 6 and 7, the necessity of a Q-learning-like method is questionable. In such a scenario, direct application of dynamic programming would seem more straightforward.

In light of these concerns on the theoretical results, my evaluation remains unchanged. However, I am open to revising my score should there be further clarification or evidence that contradicts my current understanding.

References:

[1] Watkins, C. J., & Dayan, P. (1992). Q-learning. Machine learning, 8, 279-292.

[2] Jaakkola, T., Jordan, M. I., Singh, S. P. (1994). On the convergence of stochastic iterative dynamic programming algorithms. Neural Computation, 6:1185–1201.

[3] Tsitsiklis, J. N. (1994). Asynchronous stochastic approximation and Q-learning. Machine Learning, 16(3):185–202.

[4] Borkar, V. S., & Meyn, S. P. (2000). The ODE method for convergence of stochastic approximation and reinforcement learning. SIAM Journal on Control and Optimization, 38(2), 447-469.

Thanks for your reply. We would like to defend our method. It seems you have two concerns in the reply. Before "Furthermore, at the end of Sec. 2.4", the concern is "no reference". However, the equation and proof are basic common knowledge in this field. "Using sampled interaction data to approximate the expectation" is the most common technique in this field. Both you and other reviewers can easily understand the the method and theorems. So we believe the presentation is clear for the researchers in this field.

After "Furthermore, at the end of Sec. 2.4", there are two questions. For the first one, when we mention convergence, we mean the ideal case where we can obtain the true transition probability from $D_i$. We know there is a estimation error but we have claimed the trade-off between efficiency and theory. For the second one, note the BQL has two versions. The Q-table version (Algorithm 1) strictly follows the operators, so we can make such a claim. The results in Figure 1(a) can demonstrate it. And for NN version (Algorithm 2), we know that even single-agent DQN with NN cannot guarantee the convergence.

Moreover, we want to ask a question. We propose the first operator with convergence and optimality and extend it into algorithm, but other baselines cannot theoretically guarantee the convergence and optimality even in the ideal case. Do you think our work is the best among these methods in terms of theory and practicality? If the answer is no, could you tell us which baseline is better than BQL and why? If the answer is yes, we want to know why these baselines meet the standard of top-tier conference.

Let’s take Eq. (2) in your paper as an example: it is the Bellman optimality equation for action values and not an update rule. However, the preceding text reads “the convergence of independent Q-learning”, leading to confusions. It is unclear as to whether Eq. (2) is being described as part of independent Q-learning, or as the optimal Q value that should be converged to.

There is a whole sentence before and after Eq. (2): " the convergence of independent Q-learning is not guaranteed". Eq. (2) is exactly the value iteration of independent Q-learning, and it is not guaranteed to be converged, which we have analyzed multiple times in this paper. We do not think that this sentence is misleading.

And the algorithms that make use of them were referred to as value iteration, rather than Q-learning

The equations in our paper are exactly value iteration. We do not call them Q-learning. "Best Possible Q-learning" is just the name of our paper, to establish the relationship and difference with existing methods: independent Q-learning, Hysteretic independent Q-learning, and Distributed independent Q-learning.

Concerning the comment that “Both you and other reviewers can easily understand the method and theorems”: this is somewhat subjective.

Yes, it is subjective. But the concern of presentation is a subjective topic, which is evaluated by whether the readers can easily understand the method and theorems.

one would need to have infinite amount of data in each epoch

This is the trade-off between efficiency and theory which we have discussed in the replies above.

Indeed, proposing “the first operator with convergence and optimality” and developing a well-performing practical algorithm is commendable. However, as I have highlighted, that was not exactly how it was claimed in the paper.

This is exactly what we claimed in this paper. In abstract and introduction, we claimed that "we propose best possible operator, a novel decentralized operator, and prove that the policies of agents will converge to the optimal joint policy", "By instantiating the simplified operator, the derived fully decentralized algorithm, best possible Q-learning (BQL), does not suffer from non-stationarity.". And the structure of method section follows the same logic. Sec. 2.2 and 2.3 are operators, and Sec. 2.4 is algorithm. The structure is really clear.

I believe it is premature to draw comparisons with existing works, before addressing the aforementioned concerns.

The theorems have been supported by proofs, and the algorithm has been supported by experimental results. Therefore, it is important to compare with existing methods to defend our contribution.

As the discussion is ending, we have to make a supplement. As you said, the proofs of operators are correct and the empirical performance is good. The concern is the estimation error in algorithm. Naturally, the influence of estimation error in algorithm should be verified using experiments, which is the main purpose of experiments. Our algorithm can achieve good performance, which demonstrates that our algorithm can overcome the estimation error. Our paper is not just a theory paper. We focus on practical algorithm which is derived from theory.

We don't need to further search for all possible $P_{env}$, because there is only one $P_{env}$. $P_{env}$ is the property of the environment. It is given and will not change.

Let us give an example. In the following tabular case, $p_{env}$ is defined as

Agent i can only perceives $P_i$, which depends on $\pi_{-i}$. For example, if $\pi_{-i}(a_{-i}^1|s_0) = 1$, $P_i(s_1\mid s_0,a_i^1) = 0.2$. However, in this environment, $P_i(s_1\mid s_0,a_i^1)$ is impossible to be 1.

In the Equation in Lemma 1 (the definition of $Q_i\left(s, a_i\right)$ ), should the $r$ be $r_i\left(s, a_i\right)$ ?

As defined in section 2.1, the reward is $r(s,s')$, which does not depend on joint action. The setting is still general because if two joint actions lead to the same transition dynamics in the environment, the two actions should have the same effects, and we do not need to discriminate the actions. The effects of actions are reflected in the distribution of $s'$.

Imagine that we are playing a computer game. There is a certain state where the left key and the right key can lead to the same next state or the same distribution of the next state. Do we need to give the right key a higher reward to encourage the players to always select the right key?

Again, in the definition of $Q_i\left(s, a_i\right)$, what is the search space of $P_i\left(\cdot \mid s, a_i\right)$ ?

Yes, the search space is "all possible transitions probabilities", but the situation you proposed might be impossible to happen in the environment. Look at the definition of $P_i$ (Eq. 1), if $P_{env}$ is stochastic, no matter what $\pi_{-i}$ is, we cannot put all probability to the state that has the highest value.

I have difficulty understanding the first inequality in the equation series in Lemma 2, i.e., the step that replaces $P_{env}$ with $P_i^{\star}$ with a $\geq$ inequality. Can you explain that inequality?

Look at the first "=" line in lemma 2, there are two terms. $\max_{a_{-i}}P_{env}$ achieves the highest first term, and $P_i^*$ achieves the highest second term. If we replace $\max_{a_{-i}}P_{env }$ with $P_i^*$ in the first term, the first term decreases and we have a $\ge$.

I thought $D_i^m$ only contains tuples of the form $\left(s, a, r, s^{\prime}\right)$, why would it contain $P_i$ ?

Yes, $D_i^m$ contains tuples of the form $\left(s, a_i, r, s^{\prime}\right)$, and the transitions probabilities $P_i(s'|s,a_i)$ estimated from tuples of $\left(s, a_i, r, s^{\prime}\right)$ is called the contained $P_i$.

I thought the set of $P_i$ is infinitely large since these are continuous values, how is it possible that a finite set can contain all possible values of $P_i$.

Look at the definition of $P_i$ (Eq. 1), the number of $P_i$ depends on the number of $\pi_{-i}$. In the lines after Eq. 6, we have claimed that we only consider the deterministic policies, because when there is only one optimal joint policy, the optimal joint policy must be deterministic. Deterministic $\pi_{-i}$ is countable, and thus $P_i$ is countable.

I don't understand the following sentence in page 5: "Simplified best possible operator ... does not care about the relation between transition probabilities of different state-action pairs in the same buffer."

In the simplified best possible operator, each transition independently contributes to the update of the operator. Even though the transitions are in the same buffer, they are not related during the update of the operator.

In Page 5 , it is said that "BQL ideally needs only $|A|$ buffers.. which is very efficient" Suppose that every player has $K$ actions, is $|A|=K^N$ ? I'm not sure one can call this very efficient, given that this is exponentially large, and running a centralized Q-learning (so the number of joint action is $\mathrm{K}^{\wedge} \mathrm{N}$ ) should also just incur the same amount of computation.

Yes, $|A|=K^N$. The reason why you think it is not efficient is that the problem itself is complex. Decentralized learning is more complex than centralized learning, and centralized Q-learning is an ideal solution for decentralized learning. If our method can achieve the same amount of computation with centralized Q-learning, we can say that our method is efficient.

We know that you expect a decentralized learning method which is much more efficient than centralized Q-learning and can guarantee the convergence to optimal policy. However, it seems to be impossible. If such a decentralized method really exists, for any single-agent Q-learning problem, we can factorize its action space, convert it to a decentralized MARL problem, and solve it using this method efficiently. It will be a huge revolution for Q-learning.

In theory of the operators (Section 2.2), the agents of course can know $P_{env}$. But knowing $P_{env}$ is for knowing $P_i$, so they can directly know all possible $P_i$ in theory.

In algorithm, the agents do not need to know $P_{env}$, but they can search for all possible $P_i$. We will explain why they can do it. Once other agents $-i$ take a policy $\pi_{-i}$, the agent $i$ will observe a possible $P_i$ by collecting experiences in the environment. Do you think so? If other agents $-i$ go through all possible policies $\pi_{-i}$, the agent $i$ search for all possible $P_i$. So in this process, the agent $i$ searches for all possible $P_i$ and does not know $P_{env}$.

Take an example. I do not know the review mechanism of ICLR ($P_{env}$), but if I submit enough papers (collecting experiences in the environment), I can know all possible rating situations ($P_i$).

Note there is only one $P_{env}$, the $P_i$ changes only when $\pi_{-i}$ changes. A $\pi_{-i}$ totally determines a $P_i$.

"We don't need to further search for all possible $P_{env}$, because there is only one $P_{env}$. " --- This only applies when you know $P_{env}$.

So can you confirm that the technique developed in Section 2.2 only applies to the case when $P_{env}$ is known to every player? That's because the search space of $P_i(\cdot|s,a_i)$ depends on $P_{env}$. So in order for every player to perform the search, knowledge on $P_{env}$ is required.

It seems like the theory is mostly a reduction of the "fully decentralized setting" to the "joint Q-learning"/CTDE setting. However, the actual connection is quite obfuscated; could you clarify how these two are related (and what is different)? It also seems like BQL can be seen as an extension of I2Q to the stochastic setting. Is this a fair comparison?

Decentralized learning is very different from CTDE. As analyzed in section 2.1, due to the lack of other agents' actions, the transition probabilities become non-stationary, which breaks the assumption of convergence and optimality of existing RL methods. Therefore, the main challenge of decentralized learning is to deal with non-stationary transition probabilities. However, in CTDE and joint learning, the transition probabilities are stationary, so they do not need to consider this problem at all. Therefore, we can say that the theory of BQL has no connection with CTDE and joint Q-learning. BQL is not an extension of I2Q. I2Q tries to directly obtain the optimal transition probabilities, but BQL obtains the value under the optimal transition probabilities by new operators. BQL is an extension of Hysteretic IQL to the stochastic setting, as discussed in Appendix B. Our method and baselines adopt the same settings and hyper-parameters, so we believe the comparison is fair.

I did not follow the last couple of steps in the proof of Lemma 4. Specifically, how are you combining the various expressions to get the second last equation, and how are you unrolling it to get the last one?

For Lemma 4, look at the RHS of the first inequality (the one after "According to the proof of Lemma 3, we have"). Notice the definition of $s^*$ and $a_i^*$, which achieve the maximum of RHS. For the LHS of this inequality, if we replace the $\arg \max_{s,a_i}$ (the max one for LHS ) with $s^*$ and $a_i^*$ (not the max one for LHS), the inequality holds. Then we know $Q_i^{k-1}+\epsilon \geq Q_i^e$, so if we replace $Q_i^e$ with $Q_i^{k-1}+\epsilon$, the inequality still holds.

For the last inequality of Lemma 4, after merging the same terms, notice the definition of $s^*$ and $a_i^*$, which exactly correspond to the infinite norm.

BQL is not "fully decentralized"?

We only need a pre-defined exploration schedule for each agent. In training, the agents independently follow the exploration schedule without centralized control, so the decentralized assumption still holds. The key ingredient to getting BQL- to work is not enough exploration but the operator, because BQL- adopts the same exploration method with IQL, H-IQL, MA2QL-, and I2Q.

There seems to be a gap between theory and practice, esp., the improved performance of BQL when there is only a single replay buffer. Are there any intuitions for why BQL works in this case?

On the one hand, as analyzed in the last paragraph of section 2.4, if the non-stationary single replay buffer sufficiently goes through all possible transition probabilities, the theory still holds. On the other hand, the intuition behind the operators is optimistic value estimation, which has been verified to be useful in decentralized learning, e.g., H-IQL. However, since the optimistic target in H-IQL is the highest state value, the overestimation problem is severe in a stochastic setting. The optimistic target in BQL is the expected value over possible transition probabilities, so BQL can avoid overestimation and achieve better performance.