Swap regret
Swap regret
- 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 <math>t</math>, the learner chooses decision <math>i</math> with probability <math>x^t_i</math> and the utility for decision <math>i</math> is <math>p^t_i</math>. A learner's swap-regret is defined to be the following:
: <math>\mbox{swap-regret}= \sum_{i=1}^n \max_{j \leq n}\sum_{t=1}^T x^t_i \cdot (p^t_j-p^t_i).</math>
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.