Swap regret is a concept from online learning and

game theory Game theory is the study of mathematical models of strategic interactions. It has applications in many fields of social science, and is used extensively in economics, logic, systems science and computer science. Initially, game theory addressed ...

. It is a generalization of

regret Regret is the emotion of wishing one had made a different decision in the past, because the consequences of the decision one did make were unfavorable. Regret is related to perceived opportunity. Its intensity varies over time after the decisi ...

in a repeated, ''n''-decision game.

Definition

In each round

t

, the learner chooses decision

i

with probability

x^t_i

and the utility for decision

i

p^t_i

. A learner's ''swap-regret'' is defined to be the following: :

\mbox=
\sum_^n \max_\sum_^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 Hindsight bias, also known as the knew-it-all-along phenomenon or creeping determinism, is the common tendency for people to perceive past events as having been more predictable than they were. After an event has occurred, people often believe ...

. The swap regret is always nonnegative. Swap regret is useful for computing correlated equilibria.

References

*. Game theory {{gametheory-stub