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 $\mathcal{F}$, vanilla PO achieves $\tilde{O}(\sqrt{AT\log (|\mathcal{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 ${\epsilon }_{\mathrm{priv}}$-DP and regret $\tilde{O}\left(\sqrt{AT\log (|\mathcal{F}|/\delta )}(1+{\epsilon }_{\mathrm{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.