Policy Similarity Measure for Two-Player Zero-Sum Games
Source abstract
Abstract
Policy space response oracles (PSRO) is an important algorithmic framework for approximating Nash equilibria in two-player zero-sum games. Enhancing policy diversity has been shown to improve the performance of PSRO in this approximation process significantly. However, existing diversity metrics are often prone to redundancy, which can hinder optimal strategy convergence. In this paper, we introduce the policy similarity measure (PSM), a novel approach that combines Gaussian and cosine similarity measures to assess policy similarity. We further incorporate the PSM into the PSRO framework as a regularization term, effectively fostering a more diverse policy population. We demonstrate the effectiveness of our method in two distinct game environments: a non-transitive mixture model and Leduc poker. The experimental results show that the PSM-augmented PSRO outperforms baseline methods in reducing exploitability by approximately 7% and exhibits greater policy diversity in visual analysis. Ablation studies further validate the benefits of combining Gaussian and cosine similarities in cultivating more diverse policy sets. This work provides a valuable method for measuring and improving the policy diversity in two-player zero-sum games.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Advanced Bandit Algorithms Research · Reinforcement Learning in Robotics · Simulation Techniques and Applications
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
School of Science, Beijing University of Posts and Telecommunications, Beijing 100876, China
School of Artificial Intelligence, Beijing University of Posts and Telecommunications, Beijing 100876, China
References (40)
Show source-provided references
1. Albrecht, S.V., Christianos, F., and Schäfer, L. (2024). Multi-Agent Reinforcement Learning: Foundations and Modern Approaches, MIT Press.
2. Some Studies in Machine Learning Using the Game of Checkers10.1147/rd.33.0210 ↗
3. Bansal, T., Pachocki, J., Sidor, S., Sutskever, I., and Mordatch, I. (2017). Emergent complexity via multi-agent competition. arXiv.
4. Mastering the game of Go with deep neural networks and tree search10.1038/nature16961 ↗
5. Mastering the game of go without human knowledge10.1038/nature24270 ↗
6. Silver, D., Hubert, T., Schrittwieser, J., Antonoglou, I., Lai, M., Guez, A., Lanctot, M., Sifre, L., Kumaran, D., and Graepel, T. (2017). Mastering chess and shogi by self-play with a general reinforcement learning algorithm. arXiv.
7. Mastering atari, go, chess and shogi by planning with a learned model10.1038/s41586-020-03051-4 ↗
8. Deepstack: Expert-level artificial intelligence in heads-up no-limit poker10.1126/science.aam6960 ↗
9. Fictitious self-play in extensive-form games
10. Berner, C., Brockman, G., Chan, B., Cheung, V., Debiak, P., Dennison, C., Farhi, D., Fischer, Q., Hashme, S., and Hesse, C. (2019). Dota 2 with large scale deep reinforcement learning. arXiv.
11. Grandmaster level in StarCraft II using multi-agent reinforcement learning10.1038/s41586-019-1724-z ↗
12. Towards playing full moba games with deep reinforcement learning
13. Real world games look like spinning tops
14. Flows and decompositions of games: Harmonic and potential games10.1287/moor.1110.0500 ↗
15. The mechanics of n-player differentiable games
16. Pipeline psro: A scalable approach for finding approximate nash equilibria in large games
17. Modelling behavioural diversity for learning in open-ended games
18. McMahan, H.B., Gordon, G.J., and Blum, A. (2003, January 21–24). Planning in the presence of cost functions controlled by an adversary. Proceedings of the 20th International Conference on Machine Learning (ICML-03), Washington, DC, USA.
19. Heinrich, J., and Silver, D. (2016). Deep reinforcement learning from self-play in imperfect-information games. arXiv.
20. Hernandez, D., Denamganaï, K., Gao, Y., York, P., Devlin, S., Samothrakis, S., and Walker, J.A. (2019, January 20–23). A generalized framework for self-play training. Proceedings of the 2019 IEEE Conference on Games (CoG), London, UK.10.1109/CIG.2019.8848006 ↗
21. A unified game-theoretic approach to multiagent reinforcement learning
22. Pugh, J.K., Soros, L.B., and Stanley, K.O. (2016). Quality diversity: A new frontier for evolutionary computation. Front. Robot. AI, 3.10.3389/frobt.2016.00040 ↗
23. Towards Unifying Behavioral and Response Diversity for Open-ended Learning in Zero-sum Games
24. A Unified Diversity Measure for Multiagent Reinforcement Learning
25. Policy space diversity for non-transitive games
26. Model soups: Averaging weights of multiple fine-tuned models improves accuracy without increasing inference time
27. Zhou, M., Chen, J., Wen, Y., Zhang, W., Yang, Y., Yu, Y., and Wang, J. (2022). Efficient Policy Space Response Oracles. arXiv.
28. Wu, Z., Li, K., Xu, H., Zang, Y., An, B., and Xing, J. (2022, January 18–23). L2E: Learning to exploit your opponent. Proceedings of the 2022 International Joint Conference on Neural Networks (IJCNN), Padua, Italy.10.1109/IJCNN55064.2022.9892077 ↗
29. Liu, M., He, T., Xu, M., and Zhang, W. (2020). Energy-based imitation learning. arXiv.
30. Effective diversity in population based reinforcement learning
31. Celebrating diversity in shared multi-agent reinforcement learning
32. Sutton, R.S. (2018). Reinforcement Learning: An Introduction, MIT Press. A Bradford Book.
33. Eysenbach, B., Gupta, A., Ibarz, J., and Levine, S. (2018). Diversity is all you need: Learning skills without a reward function. arXiv.
34. Levine, S. (2018). Reinforcement learning and control as probabilistic inference: Tutorial and review. arXiv.
35. Open-ended learning in symmetric zero-sum games
36. Brantley, K., Sun, W., and Henaff, M. (2019, January 6–9). Disagreement-regularized imitation learning. Proceedings of the International Conference on Learning Representations, New Orleans, LA, USA.
37. Fudenberg, D., and Tirole, J. (1991). Game Theory, MIT Press.
38. Extensive games and the problem of information
39. Southey, F., Bowling, M.P., Larson, B., Piccione, C., Burch, N., Billings, D., and Rayner, C. (2012). Bayes’ bluff: Opponent modelling in poker. arXiv.
40. Daskalakis, C., Deckelbaum, A., and Kim, A. (2011, January 23–25). Near-optimal no-regret algorithms for zero-sum games. Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, CA, USA.10.1137/1.9781611973082.21 ↗