Online learning under relative entropy: sharp rates and the price of reference access

We study online binary classification when each input law, conditional on the full preceding feedback history, has KL divergence at most one from a fixed reference measure. When the reference is known, we prove the sharp worst-case minimax expected regret ${\Theta }_d(\sqrt{T\log (eT)})$ at every fixed positive VC dimension bound $d$, improving the previous $O_d(T^{2/3})$ guarantee. The upper uses one KL budget across all cover resolutions; a matching threshold lower bound shows that the logarithm is necessary. When the reference is unknown, we determine the sharp dependence on reference samples and total-variation approximation accuracy. Even thresholds can require expected regret of order $T/\log (eT)$ despite polynomially many samples and inverse-polynomial approximation error. A bounded forward Rényi divergence of fixed order greater than one recovers the known-reference order. For every fixed $k$, online inputs alone recover this horizon order uniformly over all unknown full-dimensional log-concave references on ${\mathbb{R}}^k$. The general upper bounds use proper statistical strategies that choose a hypothesis before the current input; the lower bounds allow arbitrary predictions after the input and adaptive reference-sample requests.