Vanilla policy optimization achieves strong regret and privacy in bandits
Vanilla Policy Optimization Is Both Optimal and Differentially Private for Stochastic Contextual Bandits
Machine Learning
Summary
The paper shows that a simple method called vanilla policy optimization can learn to make near-optimal choices in scenarios where decisions depend on context, without needing extra tricks for exploration. This method gradually updates its decisions in a way that naturally balances trying new options and using known good ones. The authors also demonstrate a version of this method that protects user privacy by limiting how much an individual's data affects the outcome. Experiments indicate this approach works well in practice, especially when privacy is important.
What this means in practice
- •For online recommendation teams: Develop recommendation systems that balance learning and privacy with fewer model updates and strong performance guarantees.
- •For privacy engineers: Build contextual bandit algorithms that provide formal differential privacy protections without heavy use of composition, simplifying integration.
Authors
Idan Attias, Orin Levy, Alexander Ryabchenko, Yishay Mansour, Uri Stemmer
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{AT\log(|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 $\varepsilon_{\rm priv}$-DP and regret $\widetilde O\left( \sqrt{AT \log(|F|/δ)}(1+\varepsilon_{\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.