When can greedy bandits skip exploration entirely?

Standard bandit theory says you need to explore to learn the optimal arm — but in many real-world settings where exploration is unethical or costly (medicine, marketing), the practitioner refuses. The Bastani–Bayati–Khosravi result is that a pure greedy contextual bandit can match the asymptotic regret guarantees of UCB-style algorithms whenever the context distribution satisfies "covariate diversity": the conditional covariance matrix of contexts on any half-space is positive definite. That condition is satisfied by natural classes of continuous and discrete distributions.

The mechanism is that incoming users are themselves randomized enough to provide natural exploration — every patient who walks in carries a different feature vector, so even pure exploitation accidentally tests different arms across the feature space. Active exploration becomes redundant.

The catch is that you don't know in advance whether your contexts satisfy the condition. The proposed Greedy-First algorithm starts greedy and watches whether the parameter estimates converge at the asymptotically optimal rate via a hypothesis test on observed contexts and rewards. If the test fails, it falls back to a standard explore-exploit algorithm. This makes practical the philosophical move: stop assuming you need exploration, then verify you didn't.

Source: Recommenders Architectures