The Complete Phase Diagram of Deterministic Apple Tasting with Expert Advice

In prediction with expert advice under apple tasting feedback, the learner observes the true label only in rounds where it predicts $1$. For deterministic learners and $n$ experts over $T$ rounds, Chase and Mehalel (COLT 2025) determined the optimal realizable mistake bound $\Theta(\sqrt{T\log n})$ for $T\le n\le 2^T$, and stated as an open problem the regime of "slightly more than $\sqrt T$ many experts", namely $n=T^{1/2+\epsilon}$ with $\epsilon=o(1)$. We close this regime: for all $\sqrt T\le n\le T$ the optimal deterministic mistake bound is $\Theta(\sqrt{T\log_+(n/\sqrt T)})$, where $\log_+ x=\max{1,\ln x}$. For example, with $n=\lceil\sqrt T\ln T\rceil$ experts the answer is $\Theta(\sqrt{T\ln\ln T})$. The lower bound is a single self-contained "lowest-load committee" argument which also re-derives, with explicit constants, the known $\Omega(\sqrt{T\log n})$ bound for $n\ge T$. We then extend the picture to the $k$-realizable (agnostic-budget) setting and prove a lower bound of $\Omega(\sqrt{T(k+\log_+(n/\sqrt T))})$ throughout $\sqrt T\le n\le 2^T$, which is tight in the critical band $\sqrt T\le n\le T$ by a tuning of a lemma of Chase and Mehalel; for $n\ge T$ this recovers their known $\Theta(\sqrt{T(k+\log n)})$ and contains no new content. Along the way we isolate an expert-budget threshold phenomenon: with two experts $M^(2,k,T)=\Theta(k+1)$ regardless of $T$, and forcing the $\sqrt{Tk}$ term requires $n\asymp\sqrt{T/(k+1)}$ experts. Combining all regimes yields, for every $n\ge 2$, $T\ge 2$ and $0\le k\le T$: $M^(n,k,T)=\Theta(\min{T,\ (n-1)(k+1)+k,\ \sqrt{T(k+\log_+(n/\sqrt T))}})$.