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

arXiv:2609.33888v1 Announce Type: new Abstract: 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(sqrt{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 arepsilon_{rm priv}-DP and regret widetilde Oleft( sqrt{AT log(|F|/elta)}(1+arepsilon_{rm 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.

Source: arXiv cs.LG | 2026-09-29