aiqbench analysis
This research demonstrates that standard vanilla policy optimization can achieve near-optimal regret in stochastic contextual bandits without explicit exploration bonuses or importance weighting, provided the realizability assumption holds. The study further establishes a framework for integrating differentially private regression oracles into this process, enabling batched algorithms that maintain privacy guarantees while minimizing composition overhead. These findings offer theoretical and practical insights for optimizing reinforcement learning agents under strict data privacy constraints.
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{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|/\delta)}(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.
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|/\delta)}(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.
Machine Learning (cs.LG)
arXiv:2609.33888 [cs.LG]
(or arXiv:2609.33888v1 [cs.LG] for this version)
https://doi.org/10.48550/arXiv.2609.33888 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 254 words
Related coverage
Continuous Delayed-Memory Stochastic Gradient Descent and Continuous-Time Reinforcement Learning from History of Astrophysical Time Series Studies
arXiv · Sep 21, 2026
Netskope (NTSK) Q2 2027 Earnings Call Transcript
fool.com · Sep 10, 2026
Hard Constraints, Smooth Gradients: Learning Feasible Inventory Policies via Differentiable Projection
arXiv · Aug 5, 2026
LC-GRPO: Bridging Train-Inference Gap for Flow-Based GRPO with Langevin Correction
arXiv · Aug 7, 2026