Exploration-Exploitation in Multi-Agent Learning: Catastrophe Theory Meets Game Theory

Authors

  • Stefanos Leonardos Singapore University of Technology and Design
  • Georgios Piliouras Singapore University of Technology and Design

Keywords:

Multiagent Learning, Game Theory, Coordination and Collaboration, Evolutionary Computation

Abstract

Exploration-exploitation is a powerful and practical tool in multi-agent learning (MAL), however, its effects are far from understood. To make progress in this direction, we study a smooth analogue of Q-learning. We start by showing that our learning model has strong theoretical justification as an optimal model for studying exploration-exploitation. Specifically, we prove that smooth Q-learning has bounded regret in arbitrary games for a cost model that explicitly captures the balance between game and exploration costs and that it always converges to the set of quantal-response equilibria (QRE), the standard solution concept for games under bounded rationality, in weighted potential games with heterogeneous learning agents. In our main task, we then turn to measure the effect of exploration in collective system performance. We characterize the geometry of the QRE surface in low-dimensional MAL systems and link our findings with catastrophe (bifurcation) theory. In particular, as the exploration hyperparameter evolves over-time, the system undergoes phase transitions where the number and stability of equilibria can change radically given an infinitesimal change to the exploration parameter. Based on this, we provide a formal theoretical treatment of how tuning the exploration parameter can provably lead to equilibrium selection with both positive as well as negative (and potentially unbounded) effects to system performance.

Downloads

Published

2021-05-18

How to Cite

Leonardos, S., & Piliouras, G. (2021). Exploration-Exploitation in Multi-Agent Learning: Catastrophe Theory Meets Game Theory. Proceedings of the AAAI Conference on Artificial Intelligence, 35(13), 11263-11271. Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/17343

Issue

Section

AAAI Technical Track on Multiagent Systems