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
p
on a discrete set
X
based on data
X
, the regret of an estimator
q
is defined as
max
p
∈
P
r
n
(
q
,
p
)
.
where
P
is the set of all possible probability distribution, and
r
n
(
q
,
p
)
=
E
(
D
(
p
|
|
q
(
X
)
)
)
.
where
D
(
p
|
|
q
)
is the Kullback–Leibler divergence between
p
and
q
.
The oracle is restricted to have access to partial information of the true distribution
p
by knowing the location of
p
in the parameter space up to a partition. Given a partition
P
of the parameter space, and suppose the oracle knows the subset
P
where the true
p
∈
P
. The oracle will have regret as
r
n
(
P
)
=
min
q
max
p
∈
P
r
n
(
q
,
p
)
.
The competitive regret to the oracle will be
r
n
P
(
q
,
P
)
=
max
P
∈
P
(
r
n
(
q
,
P
)
−
r
n
(
P
)
)
.
The oracle knows exactly
p
, but can only choose the estimator among natural estimators.A natural estimator assigns equal probability to the symbols which appear the same number of time in the sample. The regret of the oracle is
r
n
n
a
t
(
p
)
=
min
q
∈
Q
n
a
t
r
n
(
q
,
p
)
,
and the competitive regret is
max
p
∈
P
(
r
n
(
q
,
p
)
−
r
n
n
a
t
(
p
)
)
.
For the estimator
q
proposed in Acharya et al.(2013),
r
n
P
σ
(
q
,
Δ
k
)
≤
r
n
n
a
t
(
q
,
Δ
k
)
≤
O
~
(
min
(
1
n
,
k
n
)
)
.
Here
Δ
k
denotes the k-dimensional unit simplex surface. The partition
P
σ
denotes the permutation class on
Δ
k
, where
p
and
p
′
are partitioned into the same subset if and only if
p
′
is a permutation of
p
.
