Description
In this report, we survey on the existing sample complexity bounds from multi-agent reinforcement learning (MARL) literature and those from game theory literature. Along the way, we give unified notations for game theory and MARL, and summarize different definitions of equilibria in game theory and MARL.
By comparative studies on the existing bounds, we identify several interesting open gaps in MARL, and we take preliminary steps towards answering these open questions. This report can serve as a starting point for future studies in MARL theory.