Does one player best responding to sample from a mixed strategy, and the other player minimizing regret converge to a Nash eq in a zero sum game?

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.

• Great example.. May 10, 2018 at 19:34