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

arXiv: https://arxiv.org/abs/2012.03083 · HTML: https://mlsanity.com/paper/2012.03083/

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Dec 2020.

## Built on by (most cited first, 17 of 17)

- [Independent Policy Gradient for Large-Scale Markov Potential Games: Sharper Rates, Function Approximation, and Game-Agnostic Convergence](https://mlsanity.com/paper/2202.04129/) (2022)
- [Exploration-Exploitation in Multi-Agent Competition: Convergence with Bounded Rationality](https://mlsanity.com/paper/2106.12928/) (2021)
- [Machine Unlearning: A Survey](https://mlsanity.com/paper/2306.03558/) (2023)
- [Artificial Intelligence and Spontaneous Collusion](https://mlsanity.com/paper/2202.05946/) (2022)
- [Faster Rates for No-Regret Learning in General Games via Cautious Optimism](https://mlsanity.com/paper/2503.24340/) (2025)
- [Asymptotic Convergence and Performance of Multi-Agent Q-Learning Dynamics](https://mlsanity.com/paper/2301.09619/) (2023)
- [Fast Convergence of Optimistic Gradient Ascent in Network Zero-Sum Extensive Form Games](https://mlsanity.com/paper/2207.08426/) (2022)
- [Intrinsic fluctuations of reinforcement learning promote cooperation](https://mlsanity.com/paper/2209.01013/) (2022)
- [On the Stability of Learning in Network Games with Many Players](https://mlsanity.com/paper/2403.15848/) (2024)
- [Convergence and Connectivity: Dynamics of Multi-Agent Q-Learning in Random Networks](https://mlsanity.com/paper/2503.10186/) (2025)
- [Detecting AI Assistance in Abstract Complex Tasks](https://mlsanity.com/paper/2507.10761/) (2025)
- [Regret Minimization in Population Network Games: Vanishing Heterogeneity and Convergence to Equilibria](https://mlsanity.com/paper/2507.17183/) (2025)
- [The dynamics of belief: continuously monitoring and visualising complex systems](https://mlsanity.com/paper/2208.05764/) (2022)
- [Physics Inspired Approaches To Understanding Gaussian Processes](https://mlsanity.com/paper/2305.10748/) (2023)
- [Chaos persists in large-scale multi-agent learning despite adaptive learning rates](https://mlsanity.com/paper/2306.01032/) (2023)
- [Stability of Multi-Agent Learning: Convergence in Network Games with Many Players](https://mlsanity.com/paper/2307.13922/) (2023)
- [Replication of Multi-agent Reinforcement Learning for the "Hide and Seek" Problem](https://mlsanity.com/paper/2310.05430/) (2023)

## Abstract (arXiv)

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.