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

The paper’s Theorem 4.1 establishes that for any M>0 there exist potential games, positive-measure sets of initial conditions, and exploration schedules with lim sup_t δ_k(t)=0 such that exploration can cause unbounded performance loss or gain—even if only a single agent explores—by steering the SQL dynamics (eq. (1)) between basins of different pure equilibria via the QRE geometry in 2×2 coordination games . The proof uses the geometry of the QRE surface (Theorem 4.2) to show how a temporary increase in exploration leads trajectories into the basin of the risk-dominant equilibrium, and how keeping exploration always low keeps them in the basin of the other equilibrium . The model’s construction also satisfies all quantifiers and constraints, but via a different route: it gives explicit two-action exact-potential games and single-agent, finite-window exploration schedules; it analyzes the SQL/replicator ODE directly to prove basin crossing by elementary differential inequalities. This constitutes a valid alternative proof. Minor slips in the model’s write-up (a typo in p⋆ for part (ii) and one formula for ṗ’s exploration term) do not affect correctness. Overall, both arguments are correct; the paper’s is topological/QRE-based, the model’s is a direct ODE/basin argument.