Leonardos, S., & Piliouras, G. (2022). Exploration-exploitation in multi-agent learning: Catastrophe theory meets game theory. Artificial Intelligence, 304, 103653. https://doi.org/10.1016/j.artint.2021.103653
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 (1) that smooth Q-learning has bounded regret in
arbitrary games for a cost model that explicitly balances game-rewards and exploration-costs, i.e., costs
from testing potentially suboptimal actions, and (2) that it always converges to the set of quantal-response
equilibria (QRE), the standard solution concept for games with bounded rationality, in arbitrary weighted
potential games. In our main task, we then turn to measure the effect of exploration on 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.
License type:
Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0)
Funding Info:
This research / project is supported by the National Research Foundation, Singapore - NRF 2018 Fellowship
Grant Reference no. : NRF-NRFF2018-07
This research / project is supported by the National Research Foundation, Singapore - AI Singapore Program
Grant Reference no. : AISG2-RP-2020-016
This research / project is supported by the National Research Foundation, Singapore - ALIAS grant
Grant Reference no. : NRF2019-NRF-ANR095
This research / project is supported by the Agency for Science, Technology and Research - AME Programmatic Funds
Grant Reference no. : A20H6b0151
This research / project is supported by the Singapore University of Technology and Design - NA
Grant Reference no. : PIE-SGP-AI-2018-01