We consider the problem of estimating a discrete distribution p with support of size K and provide both upper and lower bounds with high probability in KL divergence. We prove that in the worst case, for any estimator p, with probability at least δ, KL (p \| p) C\K, (K) (1/δ) \/n, where n is the sample size and C > 0 is a constant. We introduce a computationally efficient estimator p^OTB, based on Online to Batch conversion and suffix averaging, and show that with probability at least 1 - δ KL (p \| p) C (K ( (K) ) + (K) (1/δ) ) /n. Furthermore, we also show that with sufficiently many observations relative to (1/δ), the maximum likelihood estimator p guarantees that with probability at least 1-δ 1/6 χ² (p\|p) 1/4 χ² (p\|p) KL (p|p) C (K + (1/δ) ) /n\, , where χ² denotes the χ²-divergence.
Hoeven et al. (Wed,) studied this question.