no-regret

Definition

A guarantee in online learning that cumulative regret — the loss gap against the best fixed strategy chosen in hindsight — grows sublinearly in the number of rounds, so average regret goes to zero. It says the learner eventually matches the best fixed choice on average, not that it avoids mistakes. The property underpins bandit and online convex optimization algorithms, and is what justifies iterative data-collection methods such as DAgger in imitation learning.