Reda Ouhemma – Mathematics and Decision

$\begin{quote} \begin{center} \textbf{Finite-time Convergence for Decentralized Payoff-based Two-Player Zero-Sum Markov Games under weak reachability assumptions} \end{center} \medskip We consider decentralized learning for two-player zero-sum Markov games, where players have limited feedback in the form of their own payoff information without knowledge of each other's actions. Convergence to a Nash equilibrium in this setting was proven under strong reachability assumptions, namely that the induced Markov chain of any stationary policy pair is irreducible and aperiodic. It remained an open problem whether, under weaker assumptions, it would be possible to achieve an approximate Nash equilibrium efficiently. In this work, we answer this question positively and present a value-iteration-based algorithm with a Tsallis-entropy smoothing that can learn an approximate Nash equilibrium in polynomial time. Our method requires only the existence of a policy pair that induces an irreducible and aperiodic Markov chain, a considerably weaker assumption compared to previous literature. Our analysis utilizes Lyapunov drift inequalities and novel properties of Tsallis entropy that we believe to be of independent interest. \end{quote}$