  We study best-response type learning dynamics for two player zero-sum matrix
games. We consider two settings that are distinguished by the type of
information that each player has about the game and their opponent's strategy.
The first setting is the full information case, in which each player knows
their own and the opponent's payoff matrices and observes the opponent's mixed
strategy. The second setting is the minimal information case, where players do
not observe the opponent's strategy and are not aware of either of the payoff
matrices (instead they only observe their realized payoffs). For this setting,
also known as the radically uncoupled case in the learning in games literature,
we study a two-timescale learning dynamics that combine smoothed best-response
type updates for strategy estimates with a TD-learning update to estimate a
local payoff function. For these dynamics, without additional exploration, we
provide polynomial-time finite-sample guarantees for convergence to an
$\epsilon$-Nash equilibrium.
