Swap regret

Swap regret is a concept from game theory. It is a generalization of regret in a repeated, "n"-decision game.

Definition

A player's "swap-regret" is defined to be the following:

: $mbox\{swap-regret\}=sum\_\{i=1\}^n\; max\_\{j\; leq\; n\}frac\{1\}\{T\}sum\_\{t=1\}^T\; x^t\_i\; cdot\; (p^t\_j-p^t\_i).,$

Intuitively, it is how much a player could improve by switching each occurrence of decision "i" to the best decision "j" possible in hindsight. The swap regret is always nonnegative.

Swap regret is useful for computing correlated equilibria.

References