In multi-agent reinforcement learning, agents repeatedly interact and revise their strategies as new data arrives, producing a sequence of strategy profiles. Policy revision using such data induces a graph theoretic formulation raising questions on the existence of paths to equilibria and the nature of such equilibria depending on the information structure considered.

To set the context, we first study the case with weakly acyclic games, which generalize potential games and which in turn generalize stochastic teams. For such games, under only local action but with global state information, convergence to an equilibrium via best-responding under inertia was established via stochastic analysis in [Arslan et. al'17]. Realizing the critical role of the induced revision graphs for convergence and information structures for existence, we present a generalization of weakly acyclic games, and observe its importance in multi-agent learning when agents employ an experimental strategy update in periods where they fail to (\epsilon-)best respond. Sequences with this property are called satisficing paths, and games admitting such paths to equilibria are referred to as generalized weakly acyclic.

A fundamental question is whether for a given game and initial strategy profile, it is possible to construct a satisficing (or \epsilon-satisficing) path that terminates at an equilibrium. We present several characterizations and sufficiency conditions (including symmetry) under both pure and randomized strategies.

Finally, implications on reinforcement learning with local information via policy revision processes are presented: Building on the general approach for weakly acyclic games, corresponding learning results for generalized weakly acyclic games under both pure strategies and randomized strategies (with \epsilon-satisficing), and with various information structures (some of which may lead to equilibria that are only subjective) are presented. The mean-field game setting involving finitely many agents under various information structures will be studied as a mathematically insightful and practically significant case.

[Joint work with Gürdal Arslan and Bora Yongacoglu]