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
is the set of all possible probability distribution, and where
The oracle is restricted to have access to partial information of the true distribution
in the parameter space up to a partition.
of the parameter space, and suppose the oracle knows the subset
The oracle will have regret as The competitive regret to the oracle will be The oracle knows exactly
A natural estimator assigns equal probability to the symbols which appear the same number of time in the sample.
[1] The regret of the oracle is and the competitive regret is For the estimator
proposed in Acharya et al.(2013),[2] Here
denotes the k-dimensional unit simplex surface.
denotes the permutation class on