7
$\begingroup$

There is a well known fact that we can use the existence of external regret minimization algorithms to prove the minimax theorem of two-player zero-sum games.

The proof can be found in the survey Learning, Regret minimization, and Equilibria A. Blum and Y. Mansour.

Immediately arises question whether can we use external regret minimization to find mixed Nash equilibrium in finite non-zero two-player game, in other words does zero external regret leads to find mixed Nash equilibrium, in per round sense.

Intuitively it doesn't seem so, I am not sure that we can get external regret equals zero in general case, but there are polynomial time algorithm for good approximation (see the above paper), on the other hand approximation of Nash equilibrium seems like more difficult task.

I would appreciate if someone could help to answer the question.

$\endgroup$
11
$\begingroup$

No, no-regret dynamics do not converge to Nash equilibrium in general games, and its not hard to think of examples.

On the other hand, no regret dynamics do always converge to coarse correlated equilibrium in any game, and no-internal regret dynamics always converge to the set of correlated equilibria.

They are also known to converge to Nash equilibrium in several special cases of n-player games: for example, separable zero sum games, congestion games, and a few others.

In general, there are no efficient learning dynamics that converge to Nash equilibrium though. Not only is computing a Nash equilibrium PPAD hard, but even ignoring computation, for any "decoupled learning dynamics" (among which no regret dynamics are a special case) must exchange exponential communication before finding a Nash equilibrium in general games.

$\endgroup$

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.