Swap regret

Template:Short description Swap regret is a concept from online learning and game theory. It is a generalization of regret in a repeated, n-decision game.

Definition

In each round $t$, the learner chooses decision $i$ with probability $x_i^t$ and the utility for decision $i$ is $p_i^t$. A learner's swap-regret is defined to be the following:

$\text{swap-regret}=\sum _{i=1}^n\underset{j\le n}{max}\sum _{t=1}^T{x}_i^t\cdot (p_j^t-p_i^t).$

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

• Template:Citation.

Template:Gametheory-stub