User:Taliaberkowitz/regert minimization

In game theory, regret is defined to be the difference between the payoff of the strategy a player chose and the payoff of the best fixed action in hindsight.

Regret minimization refers to algorithms that minimize this regert.

There are two types of reget, external reget and internal regret. Different minimization algoritms exist for both types of regret.

Defining the problem

• Given a player i.
• The player can choose one of M actions at any stage of the game.
• If player i chooses action K at stage t his gain will be defined as $U^{t}(k)$ (so that $0\leq U^{t}(k)\leq 1$)

References

• Learning, Regret minimization, and Equilibria / A. Blum and Y. Mansour