- Rating
- 3
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
The paper studied the classical policy optimization method for the stochastic contextual bandits problem using an offline regression oracle. Under realizability and finite prediction function class assumptions, vanilla PO achieves a high-probability near-optimal regret bound. Then the authors adapt the algorithm under the batch idea and provide near-optimal theoretical guarantees for it. They consider the batched algorithm and a private oracle and show that the exponential mechanism yields pure DP. Finally, they run experiments to verify their methods and theoretical results.
Critical strengths
-
The problem is interesting, and the paper provides a new insight for vanilla PO about optimality in regret and DP for stochastic contextual bandits.
-
The theoretical contributions are solid and convincing.
-
The paper also runs experiments to verify their theoreticla findings.
Critical weaknesses
There is no evidence or discussion about how optimal the private regret bound is.
Questions for authors
Is there any evidence (a lower bound or a comparison with the baseline) to show the optimality or how good the private regret bound is, as in Corollary 8?
2 comments
Thanks for the response. I keep my positive score.
Rebuttal
Thank you for the supportive assessment and question.
Q1 / W1: optimality of the private regret bound.
For contextual bandits with general function approximation, determining the minimax dependence on the privacy parameter εpriv under the considered release model remains an important open problem.
Our multiplicative εpriv−1/2 factor arises from combining the squared-loss exponential mechanism with our regression-to-regret analysis. For this specific private oracle, we can show that the dependence is unavoidable: a two-action, two-predictor construction gives a lower bound of Ω(min(T,T/εpriv)), matching the privacy-dependent term up to logarithmic factors. This does not rule out better private regression oracles or alternative algorithms.
Existing results provide useful reference points. For ordinary stochastic multi-armed bandits, without contexts, Sajed and Sheffet (2019) achieve an additive privacy cost of O(A/εpriv). For stochastic linear contextual bandits, Chen et al. (2025) obtain regret of the form O(T+1/εpriv) under joint differential privacy, with dimension-dependent factors suppressed. In both cases, privacy contributes an additive term to the nonprivate regret bound. These results exploit the noncontextual or linear structure; they do not directly provide our guarantee for general realizable prediction classes accessed through an offline regression oracle.
We will add a discussion regarding this point. We are happy to address any follow-up questions. If our response resolves your optimality question, we kindly ask you to consider raising your score.