Skip to yearly menu bar Skip to main content


A Finite-Sample Analysis of Payoff-Based Independent Learning in Zero-Sum Stochastic Games

Zaiwei Chen · Kaiqing Zhang · Eric Mazumdar · Asuman Ozdaglar · Adam Wierman

Great Hall & Hall B1+B2 (level 1) #2016
[ ]
Thu 14 Dec 8:45 a.m. PST — 10:45 a.m. PST


In this work, we study two-player zero-sum stochastic games and develop a variant of the smoothed best-response learning dynamics that combines independent learning dynamics for matrix games with the minimax value iteration for stochastic games. The resulting learning dynamics are payoff-based, convergent, rational, and symmetric between the two players. Our theoretical results present to the best of our knowledge the first last-iterate finite-sample analysis of such independent learning dynamics. To establish the results, we develop a coupled Lyapunov drift approach to capture the evolution of multiple sets of coupled and stochastic iterates, which might be of independent interest.

Chat is not available.