Satisficing Paths and Independent Multi-Agent Reinforcement Learning in Stochastic Games

In multi-agent reinforcement learning (MARL), independent learners are those that do not access the action selections of other agents in the system. Due to the decentralization of information, it is generally difficult to design independent learners that drive the system to equilibrium. This paper investigates the feasibility of using \emph{satisficing} dynamics to guide independent learners to approximate equilibrium policies in non-episodic, discounted stochastic games. Satisficing refers to halting search in an optimization problem upon finding a satisfactory but possibly suboptimal input; here, we take it to mean halting search upon finding an input that achieves a cost within $\epsilon$ of the minimum cost. In this paper, we define a useful structural concept for games, to be termed the $\epsilon$-satisficing paths property, and we prove that this property holds for any $\epsilon \geq 0$ in general two-player stochastic games and in $N$-player stochastic games satisfying a symmetry condition. To illustrate the utility of this property, we present an independent learning algorithm that comes with high probability guarantees of approximate equilibrium in $N$-player symmetric games. This guarantee is made assuming symmetry alone, without additional assumptions such as a zero sum, team, or potential game structure. %