Iteratively Learn Diverse Strategies with State Distance Information

Summary

Reinforcement Learning (RL) algorithms commonly learn a distinct policy that is responsible for a distinct behavior. Learning different, diverse behaviors generally is a difficult task in RL. This paper proposes a new algorithm State-based Intrinsic-reward Policy Optimization (SIPO) that can learn diverse, human interpretable behaviors. The paper first discusses some of the current diversity measures, and based on the insight, it proposes the new ITR-based method, even though PBT is the choice when it comes to learning diverse behaviors. The method is efficient and can learn diverse behaviors. The effectiveness is demonstrated in simulated environments.

Strengths

- well written. Motivation and contributions made clear - the paper covers a good amount of related work, even though there are a few missing, in my opinion (see Weaknesses). - Nice evaluations w.r.t. diversity

Weaknesses

- The big field of unsupervised reinforcement learning also covers a lot of similarity/dissimilarity measures for formulating an intrinsic reward. Even though some of the works are mentioned (e.g. DIAYN), there are several other works that should be mentioned as they are using different objectives and hence differently measure the similarity/dissimilarity: - https://arxiv.org/pdf/1906.05274.pdf - http://proceedings.mlr.press/v139/yarats21a/yarats21a.pdf During a Google search, I discovered another work that also seems to have an interesting objective to learn different solutions: - https://proceedings.mlr.press/v164/celik22a/celik22a.pdf - weak motivation for the necessity of the state distance (see Questions)

Questions

- The motivation behind Figure 2 is unclear to me even when reading the text. I think this figure definitely needs more description and explanation. There are also no numbers indicating what the measured distances are. - Different works have approximated the state entropy for discovering new skills. E.g. the APT [1]. It would be interesting to see how the used diversity measures compare against it. Can the authors assess, how different the solutions would be when using the approximated state entropy compared to the proposed metrics? - The humanoid locomotion task in Section 6.1 is used to compare the diversity of learned policies. How do the methods compare w.r.t. performance? [1]: https://openreview.net/forum?id=fIn4wLS2XzU

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

2 fair

Limitations

The paper explicitly addresses limitations but doesn't state anything about potential negative societal impact.

Summary

This paper addresses the problem of learning diverse policies for a given RL task. First, it studies pros and cons of various formulations in two different dimensions: (i) How to measure diversity, for which it considers measures based on action or state distribution and state distances, (ii) how to compute the diverse policies, either with a joint method or an iterative one. Then, it combines the findings into a method, called SIPO, which implements iterative learning through gradient descent ascent with state distance incentives. Finally, it empirically evaluates SIPO on a variety of domains, including locomotion tasks, Star-Craft, and Google Research Football.

Strengths

- Relevance of the problem. Several recent works have addressed the problem of learning diverse policies in RL, in both supervised and unsupervised settings; - Methodology. Interesting and reasonably efficient methodology that is based on a new state-metric perspective on the problem of learning diverse policies; - Experimental results. Promising empirical results on challenging domains.

Weaknesses

- Motivation. The introduced objective lacks a strong theoretical ground that is mostly present in previous works with alternative diversity objectives; - Related works. The comparison between SIPO and some relevant related works, especially Zahavy et al., 2022, is not really upfront; - Experiments robustness and significance. The experiments consider arbitrary performance metric and average results over 5 or 3 seeds, which is hardly enough to get statistical significance.

Questions

I have one crucial concern about this paper, which is otherwise sound and interesting. The superiority of diversity measures based on state distances is only informally motivated, through examples rather than theoretical justification. Instead, the diversity measures based on action distribution or state occupancy have been both linked to important theoretical properties, such as reward robustness for the former (e.g., Husain et al., Regularized policies are reward robust, 2021) or bounded sub-optimality for the latter (e.g., Kakade and Langford, Approximately optimal approximate reinforcement learning, 2022). Diversity based on state distances currently lacks similar theoretical ground, which also leaves an existential question on the motivation of the paper? Why we want to learn diverse strategies in the first place? Is it to be robust to reward perturbations? Is to learn reusable skills? Is it something else? The concern reported above somewhat propagates to the experimental evaluation. If the ultimate purpose of the training is not clear, how can we evaluate one method against another? Indeed, the experiments are based on arbitrary diversity scores. SIPO may be better than baselines on those, but it is hard to reach some conclusion beyond qualitative justifications. Perhaps a good option would be to evaluate SIPO also on more consequential benchmarks, such as testing the reward robustness of the trained set of policies, or showing that the latter is a good starting point for fine-tuning to a different task. For this main reason, I am currently providing a borderline evaluation, while I am open to change my score if the authors can provide more formal justification for their objective function in the rebuttal. I provide below additional comments on the paper. **Objective function** One key aspect that Section 4.1 seems to overlook is that all of the provided motivations (especially in lines 158-169) make sense only when the environment's states lie on a metric space. In several domains, such as tabular MDPs with symbolic state representations or vision-based tasks, defining a proper metric over the states might be even more challenging than learning diverse policies alone. I think this limitation should be explicitly reported everywhere in the paper, including the introduction and abstract. The motivation reported in lines 170-173 appears to be somewhat weak too, at least in domains where external rewards are present, and the concept of idle actions may be incorporated in the rewards. Can the authors clarify the role of the cost function $g$ into the diversity score reported in Eq. 5? **Experiments** Why are the authors reporting experiments in multi-agent domains, even if they present a method for learning diverse policies in a single-agent setting? This choice looks somewhat odd, and it shall be motivated. I am worried about the statistical significance of the reported performance results, since most of them are obtained as average over 5 or 3 seeds. While I can understand that running experiments in such complex domains is costly, the standard to claim experimental robustness has increased lately. Moreover, the results report average and standard deviation. On the one hand, confidence intervals would be more meaningful than standard deviation, on the other hand only it is not enough to have best average performance to say that one method outperforms another when the intervals are overlapping. **Related Works** This work looks in a way orthogonal to Zahavy et al. (2022), in which the authors present a method to learn diverse near-optimal policies by maximizing diversity with an hard reward constraint. While their concept of diversity is different, it would be interesting to discuss pros and cons of the two alternative solutions in depth, and perhaps compare SIPO with Domino in the experimental campaign. Another work that is somewhat relevant to the topic is (Mutti et al., Reward-free policy space compression for reinforcement learning). Their aim is to learn a diverse set of policies from which any reward function can be approximately optimized, and they also present a gradient descent ascent procedure for this purpose. The fact that their work does not account for rewards is an important difference, but the authors can perhaps consider discussing this work in the paper as well. One key benefit that I see in the SIPO solution w.r.t. prior works, is that SIPO shall enjoy favorable computational complexity, whereas both Zahavy et al. and Mutti et al. need to solve a non-convex non-concave optimization problem. **Minor** - The preliminaries are framing the problem as POMDP. I do not understand why partial observability is introduced, and then never used in the paper at all. - Figure 4, IL is instead ITR? - Theorem 4 says that ITR can achieve the same rewards as PBT, but only with an inferior diversity. This trade-off between computation and diversity could be better highlighted. - One of the evaluation metric is the entropy estimator via k-NN, for which (Liu & Abbeel, 2021) is mentioned. Note that those entropy estimators have been presented before (e.g., Singh et al., Nearest neighbor estimates of entropy, 2001). Moreover, if the goal is to maximize the state entropy, why not using APT instead of SIPO?

Rating

4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

2 fair

Presentation

3 good

Contribution

2 fair

Limitations

The limitations are reported in the final sentences of the paper. Perhaps, some limiting aspects could be discussed in additional length.

Summary

The paper discusses the challenge of optimizing rewards while discovering diverse strategies in complex reinforcement learning problems. This paper examines two design choices for tackling this challenge: diversity measure and computation framework. By incorporating state-space distance information into the diversity measure, the behavioral differences between policies are accurately captured. Besides, two common computation frameworks: population-based training (PBT) and iterative learning (ITR) are compared, and it shows that ITR can achieve comparable diversity scores with higher computation efficiency. Based on above analysis, a novel diversity-driven RL algorithm named State-based Intrinsic-reward Policy Optimization (SIPO) is proposed. The authors evaluate SIPO across three environments and demonstrate that it consistently produces diverse policies that cannot be discovered by existing baselines.

Strengths

This paper introduces a state-based population diversity measurement and transfers it into a shaping reward in practice for computational conveniency. By comparison with PBT and ITR, it is concluded that ITR is able to achieve higher performance. Additionally, experiment environments including single-agent reinforcement learning and multi-agent reinforcement learning all shows the effectiveness of the proposed method. In a way, this paper is well-written and presents some contributions to the field of reinforcement learning. The authors provide clear explanations of their methodology and experiment results, making the paper easy to track.

Weaknesses

In this paper, the proposed state-based diversity measurement is one of key innovations. By combining with ITR framework, it achieves satisfactory performance. However, there still exist some weaknesses remained to be polished up. (1) The comprehensiveness of literature reviews remains to be improved. (2) The motivating example in Sec4.1 shows the limitation of previous action-based diversity measurement. However, the reason why state-distance based measurement can overcome the problem is not explained adequately. (3) The experiment part seems to be insufficient. Some SOTA diversity enhancement methods in RL and MARL are not analyzed or summarized. Besides, the assessment criteria of diversity seems unfair. (4) It claims that the heatmaps of agent positions in SMAC show obvious strategic differences. However, all four policies seem to explore similar areas in the map. (5) While the main body of the paper is well-written, there is space for improvement. I defer some of my issues in the appendix to "Questions".

Questions

Q1: Would you improve the literature reviews from the aspect of adding some well-known or SOTA related works (e.g. [1] [2] [3] [4] [5])? Q2: Why can state-distance based measurement overcome the shortcomings of action-based measurements? It is suggested to make more discussion theoretically. Q3: Can SIPO be extended to algorithms in two-player zero-sum game scenario, like self-play, PSRO? Q4: What will be like if combining state-based diversity measurement and action-based diversity measurement? It is suggested to add an study in experiment part. Q5: Since the number of population size is fixed in PBT or ITR, the determination of it is still an open question as we known. Would you add a theoretical or empirical analysis on it? Q6: Comparison criteria of diversity seems unfair to baselines in Humanoid Locomotion and SMAC, since all baselines’ optimization objective are action-based. An intuitive evaluation criteria is the quantifiable behavioral difference between agents. Could you make more analysis on it? Q7: As can be seen, the heatmaps in Fig7 seems to show that the positions explored by the four agents are not significantly different. Would you add additional explanations on it? Q8: Minor: abbreviation in Fig4 (i.e., “IL”) is not been explained. [1] Liu, Z., Yu, C., Yang, Y., Wu, Z., & Li, Y. (2022). A Unified Diversity Measure for Multiagent Reinforcement Learning. Advances in Neural Information Processing Systems, 35, 10339-10352. [2] Balduzzi, D., Garnelo, M., Bachrach, Y., Czarnecki, W., Perolat, J., Jaderberg, M., & Graepel, T. (2019, May). Open-ended learning in symmetric zero-sum games. In International Conference on Machine Learning (pp. 434-443). PMLR. [3] Hu, S., Xie, C., Liang, X., & Chang, X. (2022, June). Policy diagnosis via measuring role diversity in cooperative multi-agent rl. In International Conference on Machine Learning (pp. 9041-9071). PMLR. [4] Masood, M. A., & Doshi-Velez, F. (2019). Diversity-inducing policy gradient: Using maximum mean discrepancy to find a set of diverse policies. arXiv preprint arXiv:1906.00088. [5] Li, C., Wang, T., Wu, C., Zhao, Q., Yang, J., & Zhang, C. (2021). Celebrating diversity in shared multi-agent reinforcement learning. Advances in Neural Information Processing Systems, 34, 3991-4002.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

The authors have concluded the limitation of the methodology from the aspect of state representation and acceleration problem.

Summary

This work proposes a solution to the problem of finding diverse policies for complex (multi-agent) reinforcement learning (RL) environments. The paper is presented as a joint study on diversity metrics and learning frameworks. For the former, the authors show the limitations of common diversity metrics like action-distribution diversity and state-occupancy based metrics and argue for metrics that incorporate state-distances for training mutually-distinct policies instead. For the latter, population-based (PBT) and iterative training (ITR) approaches are considered, where PBT is presented as a more formally suitable framework, that in reality is limited by its pairwise diversity constraints. ITR as a reasonable relaxation of PBT, on the other hand, is found to be effective in combination with the author’s proposed (’meaningful’) state-distance diversity. The combination if ITR and the proposed metric is incorporated into the State-Based Intrinsic-Reward Policy Optimization (SIPO) algorithm and evaluated on the single-agent human locomotion domain, as well as the multi-agent SMAC and GRF environments. SIPO is shown to outperform related baselines and is presented to be more capable of producing visually distinct / humanly intuitive policies compared to its counterparts.

Strengths

- The paper is well researched in related work. While the evaluated frameworks PBT and ITR or the concept of state-distance in itself are not novel (but well cited and explained), the combination of ITR with the proposed state-dissimilarity diversity -- realized either as RBF-Kernel or with Wasserstein-Distance — are novel as far as I can tell. - Both the study on the limitations and the evaluation are presented in-depth and read quite intuitive. I am not too familiar with formal proofs of convergence criteria but the technical aspects in the paper itself do appear to be sound. The evaluation is reasonably complex, covering both complex single-agent and two multi-agent domains against reasonable baseline models. - The paper is very nicely written and well organized. The logical structure of motivation, related work, background, analytic study of the frameworks in combination with the metric and the presentation of the SIPO algorithm and its evaluation is easy to follow and intuitively explained. Small examples to illustrate the argumentation help lighten an otherwise densely formulated reasoning. I also find the visualizations to be nicely done. - The author’s SIPO approach seems to produce some very diverse strategies, which also appear intuitively interpretable. While diversity in itself is very important for exploration and an important Problem to solve for RL in general, I find the convergence towards interpretable strategies to be very intriguing. The paper is not only nicely understandable and informative on the matter of diversity related approaches, the evaluation is rather strong and the supplementary material has enough content for another paper by itself. I have no real complaints about this work, very nicely done.

Weaknesses

- Besides providing a reasonably complex evaluation, there could have been more than 5 seeds used for the evaluation. - I would also like to see at least some classic total-reward metrics / comparisons for these domains, as the metrics chosen here to highlight the performances of the SIPO algorithm (pairwise distances, est. state entropy, agent position distributions, nr. distinct strategies) seem a bit cherry-picked to argue in favor of diversity only. While there are some relevant plots in the Appendix (and some of the toy-examples reason with rewards), I would encourage to showcase at last one such classic performance comparison against the baselines in the main-paper itself.

Questions

- In 4.2 it is mentioned that PBT only converges when the exploration is faint. Is this claim shown somewhere or is this based on empirical evidence? - Could you provide some motivation on why you are casting $D_s(\pi_i, \pi_j^*)$ as intrinsic reward, and why RBF Kernel and the Wasserstein Distance were chosen for the diversity? Why does L_2 WSD provide ‘stronger discriminative power’(l263)? - Increasingly more MARL approaches start to require a DEC-POMDP for independent / localized actions without a fully observable state. How would you judge the SIPO’s transferability to such a formalization?

Rating

8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

4 excellent

Contribution

3 good

Limitations

There are two larger limitations mentioned, for once the assumption of continuity for convergence and the access to an object-centric state-representation. Both are openly disclosed and discussed in the paper. ‘The acceleration of ITR remains an open challenge’ is also a valid outlook, that should be addressed in the future.

After response

I want to thank the authors for their detailed replies. Unfortunately, I am still doubtful on both the strength of the motivation and the choice of evaluation metrics. I concede that those are matter of opinion rather than formal/technical weaknesses. I see little chance of solving them through back-and-forth discussion. Instead, I will hear other opinions in the private discussion before making a final evaluation. As a minor note, I think that proposing SIPO as a way to "find all unique solutions for the same task in RL" is somehow overstated. This looks closer to the objective of Domino, in which one maximizes the diversity of a set of nearly optimal policies. Instead, SIPO does not control the sub-optimality, as it has an hard constraint on diversity. This means that some of the policies provided by SIPO are not solutions to the task, even in approximate sense.

Thank you for the rebuttal

Thank you to the authors for this honest reply. While Apx.B5 does in fact show some reward details, the averaged scores on this provided table much more clearly show that there is in fact quite a tradeoff between diversity and performance. I hope this will be communicated more upfront in the CR. However, I do personally agree with the authors on the importance of diversity and interpretability of RL-policies, even though performance is not quite on par. I am still quite in favor of publishing this work due to its excellent readability and the progress on human interpretable results. I would welcome it if it code would be open-sourced as an helpful tool for the community.

Answer to the authors

I am sorry for my late reply. I am thankful for the author's detailed explanations. I don't have further questions and would like to wait for the discussion period for further action. However, the author's response helps me to recommend a 'weak accept'.