  We study two-player zero-sum stochastic games, and propose a form of
independent learning dynamics called Doubly Smoothed Best-Response dynamics,
which integrates a discrete and doubly smoothed variant of the best-response
dynamics into temporal-difference (TD)-learning and minimax value iteration.
The resulting dynamics are payoff-based, convergent, rational, and symmetric
among players. Our main results provide finite-sample guarantees. In
particular, we prove the first-known $\tilde{\mathcal{O}}(1/\epsilon^2)$ sample
complexity bound for payoff-based independent learning dynamics, up to a
smoothing bias. In the special case where the stochastic game has only one
state (i.e., matrix games), we provide a sharper
$\tilde{\mathcal{O}}(1/\epsilon)$ sample complexity. Our analysis uses a novel
coupled Lyapunov drift approach to capture the evolution of multiple sets of
coupled and stochastic iterates, which might be of independent interest.
