A Self-Play Posterior Sampling Algorithm for Zero-Sum Markov Games

Existing studies on provably efficient algorithms for Markov games (MGs) almost exclusively build on the "optimism in the face of uncertainty" (OFU) principle. This work focuses on a different approach of posterior sampling, which is celebrated in many bandits and reinforcement learning settings but remains under-explored for MGs. Specifically, for episodic two-player zerosum MGs, a novel posterior sampling algorithm is developed with general function approximation. Theoretical analysis demonstrates that the posterior sampling algorithm admits a √ T -regret bound for problems with a low multi-agent decoupling coefficient, which is a new complexity measure for MGs, where T denotes the number of episodes. When specialized to linear MGs, the obtained regret bound matches the state-ofthe-art results. To the best of our knowledge, this is the first provably efficient posterior sampling algorithm for MGs with frequentist regret guarantees, which enriches the toolbox for MGs and promotes the broad applicability of posterior sampling. h (x) = sup µ V µ,ν h (x) for all (x, h). To simplify the notation, we use Nash Equilibrium. Moreover, there exists a set of Nash equilibrium (NE) policies (µ * , ν * ) (Filar & Vrieze, 2012) that are optimal against their best response such that for all (x, h) ∈ X × [H]. For this NE, the following famous minimax equation holds: