An Exponential Deterministic-Randomized Separation in Oracle-Based Online Learning

Randomization is known to improve oracle efficiency in online learning, but whether it can provide a provable advantage over deterministic algorithms has remained open. We resolve this question for transductive online learning of thresholds on an unknown total order with a consistency-type empirical risk minimization (ERM) oracle. For natural extremal ERM rules, including minimal-prefix and maximal-prefix selection, every deterministic learner incurs linear total cost: on some instance, the number of mistakes $M$ and oracle calls $Q$ satisfy $M+Q\ge T-\epsilon$. Consequently, any deterministic learner achieving $O(\log T)$ mistakes requires $\Theta (T)$ oracle calls. In contrast, the randomized learner of AHR25 achieves $O(\log T)$ expected mistakes and $O(\log T)$ expected oracle calls under the same fixed rule. We prove a matching $\Omega (\log T)$ expected-query lower bound, establishing the optimal randomized query complexity. We further show that the separation depends on the oracle's selection rule: a legal feasible-median rule admits deterministic $O(\log T)$ complexity, while extremal and global-median rules force linear cost. Thus, randomization yields an exponential separation in oracle complexity, while oracle selection emerges as a fundamental complexity axis.