Vanilla Policy Optimization Is Both Optimal and Differentially Private for Stochastic Contextual Bandits

Can vanilla policy optimization explore enough to achieve near-optimal regret in stochastic contextual bandits? We show that standard exponential policy updates driven by offline regression do so under realizability, without exploration bonuses or importance weighting. For A actions, T rounds, and a finite prediction class F, vanilla PO achieves widetilde O(√ATlog(|F|)) regret with high probability. Our analysis reveals an implicit exploration mechanism of independent interest: gradual policy updates prevent actions from losing probability too quickly, allowing the regression oracle to learn their expected losses. We further develop a batched version using only O(log T) regression calls and policy switches, and show how private regression oracles yield differentially private contextual bandit algorithms without composition across batches. For a finite class, this gives pure varepsilonrm priv-DP and regret widetilde Oleft( √AT log(|F|/δ)(1+varepsilonrm priv-1/2) right). Finally, experiments across oracle-based contextual bandit algorithms, with and without privacy, demonstrate the practical effectiveness of policy optimization and the value of explicit exploration under stronger privacy constraints.