Minimum Certified Exploration for Contextual Bandits

We present an algorithm that explores only as much as a regret guarantee actually requires, for general contextual bandits with a regression oracle. We introduce a one-step regret certificate: a closed-form test of whether the one-step inequality behind the regret analysis holds at the current predictions, so that every certified allocation inherits the full regret guarantee. The certified allocations have a least element, one distribution that minimizes every nongreedy probability at once, and our algorithm MinCE (Minimum Certified Exploration) computes it in a few sweeps of scalar inversions, with no additional oracle call or hyperparameter and with every intermediate allocation certified. MinCE matches the best existing first-order regret bound and the minimax rate while performing minimal exploration. In simulations MinCE attains the lowest regret, and on 130 OpenML classification datasets it achieves the lowest loss on 112 of them, outperforming the baselines.