We consider the fundamental problem of estimating a discrete distribution on a domain of size K with high probability in Kullback-Leibler divergence. We provide upper and lower bounds on the minimax estimation rate, which show that the optimal rate is between⁽K + ln(K) ln(1/δ)⁾ /n and ( K ln ln(K)+ln(K) ln(1/δ) ) /n at error probability δ and sample size n, which pins down the rate up to the doubly logarithmic factor ln ln K that multiplies K. Our upper bound uses techniques from online learning to construct a novel estimator via online-to-batch conversion. Perhaps surprisingly, the tail behavior of the minimax rate is worse than for the squared total variation and squared Hellinger distance, for which it is⁽K + ln(1/δ)⁾/n, i.e. without the ln K multiplying ln(1/δ). As a consequence, we cannot obtain a fully tight lower bound from the usual reduction to these smaller distances. Moreover, we show that this lower bound cannot be achieved by the standard lower bound approach based on a reduction to hypothesis testing, and instead we need to introduce a new reduction to what we call weak hypothesis testing. We investigate the source of the gap with other divergences further in refined results, which show that the total variation rate is achievable for Kullback-Leibler divergence after all (in fact by the maximum likelihood estimator) if we rule out outcome probabilities smaller than O(ln(K/δ)/n), which is a vanishing set as n increases for fixed K and δ. This explains why minimax Kullback-Leibler estimation is more difficult than asymptotic estimation.

We consider the adversarial linear contextual bandit setting, which allows for the loss functions associated with each of K arms to change over time without restriction. Assuming the d-dimensional contexts are drawn from a fixed known distribution, the worst-case expected regret over the course of T rounds is known to scale as Õ(√KdT). Under the additional assumption that the density of the contexts is log-concave, we obtain a second-order bound of order Õ(K√dV_T) in terms of the cumulative second moment of the learner's losses V_T, and a closely related first-order bound of order Õ(K^pdL^∗_T) in terms of the cumulative loss of the best policy L^∗_T. Since V_T or L^∗_T may be significantly smaller than T, these improve over the worst-case regret whenever the environment is relatively benign. Our results are obtained using a truncated version of the continuous exponential weights algorithm over the probability simplex, which we analyse by exploiting a novel connection to the linear bandit setting without contexts.