Do not Start with Trembling Hands: Improving Multi-agent Reinforcement Learning with Stable Prefix Policy

What is the value of the hyper-parameter $t_{inter}$? How does its value affect the performance?

The $t_{inter}$ value is the number of warm-up episodes. We need state data to train a KMeans classifier and this state data is collected within the $t_{inter}$ episodes. Additionally, the classifier and the MCT$^2$ are reconstructed every $t_{inter}$ episode to overcome the influence of policy shifts. In this paper, this hyper-parameter is empirically set as 500.

The target value $y^t$ in vanilla QMIX is $y^t=r^t+\gamma \max_{a_{t+1}}Q_{tot}(s^{t+1},a^{t+1})$, which is related to $s^{t+1}$. Why is $y^t$ still related to $s^t$ in Eq. (3)?

Sorry for the confusion caused by our mistakes. The $y^t$ is related to $s^{t+1}$ in Eq.(3) (currently Eq.(4) in the revised version). The revised formula is

and we have updated it in the paper.

Is there any theoretical basis to prove that $Q_{assem}^t$ is more accurate than the original $Q_{tot}$?

In this paper, similar states belong to a prototype cluster with a value, so similar states share the same value. The $Q_{assem}^t$ is the average value of $Q_{tot}$. In such a way, the expectation of $Q_{assem}^t$ is the same as the expectation of original $Q_{tot}$. The $Q_{assem}^t$ provides lower variance.

I think that in some scenarios, the SPP variant may be more likely to fall into a local optimal solution. Suppose that in such a scenario, agents can easily access the state corresponding to the suboptimal solution, while the state corresponding to the global optimal solution is in the opposite direction and relatively difficult to access (for example, further away from the initial position of the agents). The SPP variant may directly give up early exploration and find it difficult to converge to the global optimal solution. Of course, the above issue can be alleviated by adjusting cucb, but this requires sufficient prior knowledge.

Thank you very much for your comments, we would love to discuss this scenario with you. You say that states oriented to suboptimal solutions are very easy to reach while states oriented to global optimal solutions are very difficult to collect and that the vast majority of data collected by algorithms focusing on exploration in this scenario are suboptimal, and we believe that obtaining an accurate value estimation of the global optimal state that is distinguishable from the suboptimal data is also a very difficult task to solve in this case. Our approach includes an annealing-like process to target such scenarios, in addition to the possibility of tuning the parameters of the UCT to encourage exploration. During annealing the tree in $\text{MCT}^2$ is destroyed and reconstructed, at which point the MARL algorithm resumes single-step exploration.

In the remaining time we would like to address the remaining concerns that you have that prevent you from accepting the paper. We would appreciate it if you could engage with us on the remaining concerns, as we want to address them.

We thank the reviewer for the detailed review of our paper. We are motivated that you found the new perspective interesting and inspiring. After reading the reviews, we address your concerns below. Please let us know if further clarification is needed.

The proposed method is based on the premise that agents should be capable of finding a policy toward success from historical interactions. In other words, SPP relies heavily on the performance of the underlying algorithm.

Our SPP approach divides the decision-making process into two stages: pre-decision based on planning and post-decision with action noise. Where the pre-decision is given through UCT planning, it is not necessarily required that the historical interactions contain a successful policy, which means that even if there are no successful policies in the historical trajectory, UCT planning is still able to select the regions with the highest value or exploration potential at the moment based on the existing interactions. In contrast to relying heavily on the base policy, our SPP approach takes advantage of this favorable property of UCT planning and instead improves the performance of the base policy. Our experimental results on SMAC benchmarks can fully validate this.

The trembling hand is a concept in multi-agent games, but this paper only provides solutions in cooperative scenarios (Dec-POMDP problems). At the same time, SPP is only applied to value decomposition methods.

Thank you very much for your comments. For the perspective of better demonstrating the performance improvement of our SPP method compared to the original MARL method, we choose to test our method on the most popular benchmarks with MARL algorithms in the current MARL community, which mostly require computing the joint utility function to reach a better equilibrium of the game, and thus focus on solving the problem of credit allocation for cooperative MARL. Technically, our SPP method works for those scenarios with suboptimal equilibria due to trembling hands. We will actively look for MARL benchmarks other than cooperative scenarios for testing and welcome your further suggestions.

SMAC is a popular multi-agent experimental platform but has been pointed out to have many shortcomings [1]. More and more researchers in the MARL community advocate conducting experiments in multiple domains to evaluate the proposed algorithm comprehensively [2].

We also fully agree with this comment that the SMACv1 environment lacks randomness in initializing the task settings. SMACv2 in contrast provides the configuration settings including the number of agents and enemies, the initialized positions, and the probability of generating an agent type. However, as far as we are concerned, this configuration provides too much randomness (I'd like to call it unstable). We believe SMACv2 is more suitable to test the migration capability and few-shot scenario adaptation ability of an algorithm. Despite that, we tested our approach on three scenarios of the SMACv2 environment. The items in the table are the average winning rate among 5 seeds and their variance.

According to the results, our proposed method can follow the performance of the baseline algorithm in the so-called unstable environments in 2M time steps.

Thank you for your comments and suggestions. After reading the summary as well as the weaknesses, I think there might be some gaps between your understanding of our paper and the contents we want to express. From my perspective, you are interested in the topic that how our approach solves the trembling hands' problems. However, we find the $\epsilon$-greedy methods in MARL are similar to the THPNE problem in game theory. We aim to solve the exploration-exploitation dilemma taken by the epsilon-greedy algorithm. Therefore, the paper is about the sequence of MARL problems instead of the one-step THPNE problem. Despite of that, I will try my best to respond to your comments.

In the abstract it is claimed that [you] " find that $\epsilon$- greedy policies can be deemed...", it is unclear how and why this was not already known. In its second part unclear. How do you compute such policies? What do you mean by "plan an existing optimal policy"?

Based on the $\epsilon$-greedy algorithm, agents choose the best action with the probability of 1-$\epsilon$ and a random action otherwise. In game theory, players who make decisions with trembling hands will choose actions greedily with a probability of $p$ and other (random) actions with $1-p$. In such a way, the $\epsilon$-greedy method and the trembling hands' decision-making are correlated. Meanwhile [1] also states the relationship between $\epsilon$-greedy and the trembling hands process.

In this paper, the stable prefix policy can be considered as a trajectory template. We establish a trajectory tree based on multiple historical interactive trajectories. In each episode, agents are in the initial state at the first time step. The trajectory tree will generate a potential optimal route of states from that initial state by greedily selecting the subsequent states with the largest value, which is the process of 'plan an existing optimal policy'.

The related works section addresses the background rather than the related works, and the background is insufficient in the exposition to provide tools to understand what will be done later.

In this paper, we are focusing on the MARL exploration problem rather than the solution to the THPNE problem. Thus, we introduce MARL and some NE definitions in the Related Work section and introduce MARL basic notations and settings in the Background section. These contents might be sufficient for introducing the subsequent MARL methods.

The Theoretical Analysis is absent, meaning that in the way it is done is mostly unclear what it should suggest.

We provide some theoretical analysis of the convergence guarantee and computational complexity of our algorithm in section 4.4. The THPNE problem is used for introducing the exploration dilemma, so we did not provide the theoretical analysis of the THPNE, which, we think, is not quite relevant to MARL problems in this paper.

it was not clear to me how the hyper-optimization of the Sota algorithms used as baselines was done, both in the standard case and in the SDD-augmented case.

These Sota algorithms aim at solving the MARL problem instead of the THPNE problem, so none of them introduce their methods to solve that. Based on their algorithms, our approach does not focus on the problem either.

some English phrasing is wrong and some typos are present (for example there should be an $\epsilon$ at the 9th line of the first page I believe)

We will double-check the expression methods and typos in this paper. However, at the 9th line of the first page, we want to express that agents choose the best actions with the largest values. Thus, agents choose actions greedily and there should not be an epsilon here.

In the remaining time we would like to address the remaining concerns that you have that prevent you from accepting the paper. We would appreciate it if you could engage with us on the remaining concerns, as we want to address them.

[1] Lee, Kiyeob, et al. "Reinforcement learning for mean field games with strategic complementarities." International Conference on Artificial Intelligence and Statistics.

Provided that the Authors refactor the section "Theoretical Analysis" as suggested, most of my concerns have been solved but I think the is still room for improvement. I am mostly worried about other's reviewer's doubts about the empirical corroboration, which can be shared, but I think I would need to know Reviewer RkkR's impression to give a final judgment.

I would like to thank the Authors for the clarifications. I will proceed by points. What I was trying to point out is that the exposition of the work is the main concerning point to me, and I hope my comments will help:

• In the abstract it is claimed that [you] " find that - greedy policies can be deemed...", it is unclear how and why this was not already known. In its second part unclear. How do you compute such policies? What do you mean by "plan an existing optimal policy"? In general what I was trying to say is that the abstract is not clear in what will be done, and it is imprecise in some parts as well. As an example of the general, unprecise exposition, I commented that in the abstract it is said that "[you] find that epsilon-greedy can be deemed as the concept ...". As you suggested as well, this result was not "found" in this work, it is a known fact. This is not a big issue, but the comment was to suggest that the phrasing of the work might be substantially revisited.

• The related works section addresses the background rather than the related works, and the background is insufficient in the exposition to provide tools to understand what will be done later. I agree with the authors saying that "[they] are focusing on the MARL exploration problem rather than the solution to the THPNE problem". For this reason indeed, I suggested inserting in the related works some comments on how the problem of exploration in MARL is managed, rather than a few lines on MARL algorithms that do not tackle the problem of exploration, and a section on the Trembling Hands Problem, that is not the focus of the paper. In this sense, the related works section is rather unrelated to the work.

• The Theoretical Analysis is absent, meaning that in the way it is done is mostly unclear what it should suggest. Indeed a theoretical analysis of the THPNE was not requested at all. What I was trying to say is that: Theorem 1 is by [2]. Assumption 1 is not discussed, how likely is it to be verified? Theorem 2 is by [1] What I mean is that the authors should better discuss how the proposed approach maps to pre-existing theoretical results, otherwise this section is rather poor and unjustified as a "Theoretical Analysis".

• some English phrasing is wrong and some typos are present (for example there should be an at the 9th line of the first page I believe). I am still a little confused here, mostly by the fact that the revised version has indeed $1-\epsilon$, so I really don't understand the answer "there should not be an epsilon here".

Generally, then, I think the global exposition of the work still hinders the overall quality, and I don't see substantial changes done to address that. Nonetheless, I am positive about raising my score in view of the other's comments.

[1] Koenig & Simmons (1993) [2] Uchendu et al. (2023)

In Section 6, the authors claim that the proposed method can be applied to the critic training in Actor-Critic MARL algorithms. Can you briefly describe how to implement the proposed method in, say, MAPPO? And what is the performance improvement when applying to MAPPO?

In the Actor-Critic MARL algorithms, actor networks are responsible for training the action distributions conditioned on observations and the critic networks train the values of states. Applying our SPP method to the Actor-Critic method includes (i)assembling the values with the same cluster nodes and (ii)removing the actors' explorations by taking the maximum of the distributions and using the trajectory templates generated by the planning process to determine whether to interrupt the process and resume single-step explorations like non-SPP-augmented methods. Our approach contributes to the performance improvement of the Actor-Critic method in two ways: on the one hand, assembles the values with the same cluster nodes so that the values for training are more accurate; on the other hand, it determines whether the elimination of the exploration of the first half of the strategy can lead to more fine-grained improvements in the second half of the strategy by planning, which has already balanced exploration and exploitation by UCT.

To focus on the efficiency aspects, we chose three subtasks to show the performance of the MAPPO and our SPP-augmented MAPPO within 2M time steps. The experimental results indicate that our method can improve the performance of Actor-Critic MARL methods. The items in the table are the average winning rates (%) among 5 seeds and their variances.

In the matrix game presented in Section 1, should the epsilon for player 1 be 0.1?

Your concerns are much appreciated. We double-check the corresponding section. With $\epsilon$ set to 0.2, the player will have a 0.8 probability of going into the greedy mode and a 0.2 probability of going into a mode where the action is chosen randomly; however, since there is also a 0.1 probability that the original greedy action will be chosen in random mode, the value of $\epsilon$ should be taken as 0.2, at which point the greedy action will take the value of 0.1

Can the proposed method be applied to scenarios with continuous action spaces?

The original intent of our paper was to address the problem of trembling hands that exists in value-based MARL methods. However, our SPP method contains major components: the UCT planning[1], Q-value assembling and cancelation of action noise are technically applicable to continuous action spaces. We have found that our approach is surprisingly able to improve the performance of Actor-critic based, so we are reasonably confident that our SPP approach is also capable of applying to continuous action spaces. We will actively search for suitable benchmarks for testing and welcome your further suggestions.

In the remaining time we would like to address the remaining concerns that you have that prevent you from accepting the paper. We would appreciate it if you could engage with us on the remaining concerns, as we want to address them.

[1] Hubert, Thomas, et al. "Learning and planning in complex action spaces." International Conference on Machine Learning.

We thank the reviewer for the detailed review of our paper. After reading the reviews, we address your concerns below and update a revision of our paper. Please let us know if further clarification is needed.

In Figure 8, the performance of the proposed policy closely mirrors that of the original QMIX implementation. I would suggest the authors test on more challenging MARL benchmarks.

In this paper, we provide our main experimental results in Figure 5 which contains the challenging subtasks of the SMAC environment. Among the subtasks, the 5m_vs_6m, 3s_vs_5z, and 2c_vs_64zg tasks are hard tasks. Not all the baseline algorithms can achieve good results. Additionally, the subtasks including MMM2, 3s5z_vs_3s6z, and 6h_vs_8z are super-hard tasks. Experimental results on these tasks within 2M time steps can show the better performance of our approach. In contrast, Figure 8 shows the other tasks in the SMAC environment and most of them are easy tasks in which the original QMIX as well as other baseline algorithms can achieve acceptable results. This might be the reason why our proposed policy closely mirrors that of the original QMIX.

The proposed method, in its pursuit of faster convergence, makes the additional trade-off of further diminishing exploration in favor of exploitation.

Our method suggests dividing the decision-making of the existing MARL methods into two phases: our Stable Prefix Policy and vanilla policy. SPP balances the exploration and exploitation during the trajectory planning process with UCT, and we further apply Dirichlet noise to the planning phase, which gives more explorations. SPP explores more globally and centrally compared to existing popular MARL methods.