In decision theory, competitive regret is the relative regret compared to an oracle with limited or unlimited power in the process of distribution estimation.
Consider estimating a discrete probability distribution on a discrete set based on data , the regret of an estimator is defined as