Swap regret

In each round ${\displaystyle t}$, the learner chooses decision ${\displaystyle i}$ with probability ${\displaystyle x_{i}^{t}}$ and the utility for decision ${\displaystyle i}$ is ${\displaystyle p_{i}^{t}}$. A learner's swap-regret is defined to be the following:

${\displaystyle {\mbox{swap-regret}}=\sum _{i=1}^{n}\max _{j\leq n}\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.

• Blum, Avrim; Mansour, Yishay (2007), "From external to internal regret" (PDF), Journal of Machine Learning Research, 8: 1307–1324, MR 2332433.

This game theory article is a stub. You can help Wikipedia by expanding it.

• v
• t
• e