<p>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):</p>

<pre><code>    D     E
A   1     0
B   0     1
C  0.6   0.6
</code></pre>

<p>I think that in any equilibrium, the row player plays only C. </p>

<p>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.</p>

CC BY-SA 4.0
2018-05-10T19:34:14.123Z
Great example..
Aaron Roth
CC BY-SA 4.0
2018-05-08T01:10:53.270Z
2018-05-08T01:10:53.270Z
usul
<p>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. (<a href="https://theory.stanford.edu/~tim/f13/l/l17.pdf" rel="nofollow noreferrer">https://theory.stanford.edu/~tim/f13/l/l17.pdf</a>). 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?</p>

<online-learning><nash-equilibrium>
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?
SVN
# 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?

(Asked by: username_0 on 2018-05-07)

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?

**Tags:** online-learning, nash-equilibrium

---

## 1 answers

### Answer by username_1 on 2018-05-08. Score: 5

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.

> **Comments:**
> **username_2**: Great example..  

---

