  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 zero-sum
MGs, a novel posterior sampling algorithm is developed with general function
approximation. Theoretical analysis demonstrates that the posterior sampling
algorithm admits a $\sqrt{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-of-the-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.
