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

arXiv: https://arxiv.org/abs/2609.33888 · HTML: https://mlsanity.com/paper/2609.33888/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 57 references that are in the map.
- First posted on arXiv 27 Sep 2026.

## Builds on (most cited first, 7 of 7)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Upper Counterfactual Confidence Bounds: a New Optimism Principle for Contextual Bandits](https://mlsanity.com/paper/2007.07876/) (2020)
- [Beyond Covariance Matrix: The Statistical Complexity of Private Linear Regression](https://mlsanity.com/paper/2502.13115/) (2025)
- [Towards Differentially Private Reinforcement Learning with General Function Approximation](https://mlsanity.com/paper/2605.07049/) (2026)
- [Making Contextual Decisions with Low Technical Debt](https://mlsanity.com/paper/1606.03966/) (2016)
- [Optimal Regret for Policy Optimization in Contextual Bandits](https://mlsanity.com/paper/2602.13700/) (2026)
- [Shuffle and Joint Differential Privacy for Generalized Linear Contextual Bandits](https://mlsanity.com/paper/2602.00417/) (2026)

## Abstract (arXiv)

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.