It is well-known that in a $2$-player zero sum game if one player plays a regret minimizing mixed strategy, and the other player best-responds at each round to that mixed strategy, we are guaranteed convergence to an approximate Nash Equilibrium in poly-time. See e.g. (https://theory.stanford.edu/~tim/f13/l/l17.pdf). My question is suppose that one player is playing a no-regret strategy, and the other play best-responds to a sample from the mixed strategy of her opponent, rather than to the mixed strategy. Is it still true that the empirical average of both strategies will converge to Nash in poly-time?


No, it's not true. Consider this game where the row player's actions are A,B,C and column's are D,E (shown are the row player's payoffs):

    D     E
A   1     0
B   0     1
C  0.6   0.6

I think that in any equilibrium, the row player plays only C.

But now if the column player uses a no-regret algorithm, every sample will either be action D or E, and the row player's best response will always be either A or B. So the row player will never play C in the entire empirical history.

  • $\begingroup$ Great example.. $\endgroup$ – Aaron Roth May 10 '18 at 19:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.