acceptodds
Under review as a conference paper at ICLR 2027

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

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 actions, rounds, and a finite prediction class , vanilla PO achieves 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 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 -DP and regret . 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.

Primary area:
learning theory
Keywords:
contextual bandits, policy optimization, differential privacy, oracle-efficient learning

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_sEKeOpenReview ↗
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
  1. The problem is interesting, and the paper provides a new insight for vanilla PO about optimality in regret and DP for stochastic contextual bandits.

  2. The theoretical contributions are solid and convincing.

  3. 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

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\varepsilon_{\text{priv}} under the considered release model remains an important open problem.

Our multiplicative εpriv−1/2\varepsilon_{\text{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))\Omega(\min(T,\sqrt{T/\varepsilon_{\text{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)\widetilde O(A/\varepsilon_{\mathrm{priv}}). For stochastic linear contextual bandits, Chen et al. (2025) obtain regret of the form O~(T+1/εpriv)\widetilde O(\sqrt T+1/\varepsilon_{\mathrm{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.

Thanks for the response. I keep my positive score.

Reviewer_rjzSOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies stochastic contextual bandits in a setting where the expected loss function belongs to a realizable class of predictors. At each iteration, the agent observes a context, chooses an action, and observes only the loss associated with that chosen action.

The main algorithm operates as follows: i) initialize a uniform policy; ii) sample an action according to the current policy; iii) fit a loss predictor using the observations collected thus far; iv) update the policy by exponentially decreasing the weight of actions with higher predicted losses; v) repeat the process. The resulting policy depends on the cumulative history of the fitted predictions.

A batched variant fits a predictor using the previous batch and deploys an average of exponential updates, initialized from the uniform policy. This approach requires O(log⁡T)O(\log T) calls to a regression procedure, along with an additional arithmetic cost of O(A)O(A) per action selection, once the predictions have been obtained. By employing a privacy-preserving regression oracle, the article demonstrates that the resulting predictors and policies satisfy the notion of differential privacy, according to the specified privacy model.

For a finite, realizable class F\mathcal{F}, the regret (in the non-private setting) is on the order of O~(ATlog⁡∣F∣)\widetilde{O}(\sqrt{AT\log|\mathcal{F}|}). The privacy-preserving construction for a finite class introduces an additional factor on the order of 1+εpriv−1/21+\varepsilon_{\mathrm{priv}}^{-1/2}. Experiments compare privacy-preserving methods with non-private ones, using 100 datasets from OpenML.

Critical strengths

i) A potentially meaningful simplification of policy optimization with theoretical guarantees. The closest contextual-bandit policy-optimization result identified in this review, Levy and Mansour (2026), obtains near-optimal regret using an explicit exploration bonus. The present paper establishes that its specified exponential update suffices without this bonus, under the stated stochastic and regression assumptions. This appears to clarify when additional exploration machinery is unnecessary for the regret guarantee.

ii) An analysis addressing an exploration difficulty. Accuracy under historical sampling distributions does not immediately ensure accurate predictions for poorly sampled actions. The main argument relates persistent probability on suboptimal actions to accumulated prediction error and uses historical coverage to connect this error to the regression guarantee. This appears to be the substantive technical ingredient, which is nice. The finite-class regression instantiation also helps make the assumptions concrete.

Critical weaknesses

i) Novelty beyond the main theorem needs sharper positioning. FALCON/FALCON+ (Simchi-Levi and Xu, 2022) already combines offline regression with infrequent fits, while He and Zhou (2025) use fresh batches for private policy optimization. These connections are acknowledged, but distinguishing inherited principles from new arguments would clarify the contributions of the batched sampler and privacy guarantees.

ii) The practical implications remain partly unresolved. Vanilla PO is competitive, while the bonus-based variant performs more strongly. Ablations of policy averaging or recovery from inaccurate predictions would better connect these findings to the analysis. Hindsight hyperparameter selection and uncertainty proxies used by some baselines also limit broader conclusions; independent tuning or sensitivity studies would strengthen the evidence.

Questions for authors
  1. Could you clarify which arguments in the batching and privacy extensions are new relative to FALCON+ (Simchi-Levi and Xu, 2022) and the fresh-batch framework of He and Zhou (2025)?

  2. Do the empirical comparisons remain consistent with independently selected hyperparameters? Could an ablation of policy averaging help isolate the proposed exploration mechanism?

  3. What privacy guarantee applies to the approximate numerical optimization used in the experiments? Do the reported privacy budgets cover a fixed hyperparameter configuration or also the model-selection procedure?

4 comments

Thank you for the constructive assessment and questions.

Q1 / W1: comparison to prior work:

Batching and privacy extensions relative to FALCON+ (Simchi-Levi and Xu, 2022): Indeed, we build on FALCON+’s epoch-based offline regression framework, including fitting on the preceding batch and comparing predicted regret with true regret. We do not claim these ingredients as new. The new ingredient in our batching extension is the policy construction and its analysis. FALCON+ uses inverse-gap sampling, whereas our policy averages exponential updates driven by a fixed predictor. We prove that this average simultaneously provides sufficient exploration (its inverse action probabilities grow at most linearly with the predicted loss gaps) and small predicted regret. These properties allow the regression-based analysis to establish near-optimal regret for batched vanilla PO with O(log⁡T)O(\log T) oracle calls. The efficient implementation allows exact sampling using only AA predictor evaluations and O(A)O(A) additional arithmetic per round.

We view the connection between oracle-based contextual bandit learning and differential privacy as an important conceptual contribution. It yields private algorithms that access general realizable function classes only through a private offline regression oracle, with cumulative-regret guarantees expressed in terms of the oracle’s accuracy. To our knowledge, this is the first such generic oracle-based regret guarantee for private stochastic contextual bandits. Our comprehensive experimental evaluation complements these guarantees by highlighting the practical benefits of this approach through comparisons with established contextual-bandit baselines.

Framework of He and Zhou (2025): We share their fresh-batch privacy principle, but our settings and guarantees differ in three key respects:

  • Performance criterion: They analyze the sample complexity required for the learned policies to achieve near-optimal performance on average. We establish bounds on cumulative regret over the actions used for data collection.

  • Feedback: Their regression-based procedure observes rewards for two action draws per context, one from a base policy and one from the current policy. Our algorithms observe only one action loss per arriving context.

  • Coverage: Their bounds depend on how well the base policy covers a comparator policy. Our analysis establishes that the policies collecting the data themselves provide sufficient exploration.

Vanilla PO achieves this with a simple algorithmic structure: it fits a predictor directly to the observed losses and applies standard exponential policy updates, without a separate base policy or advantage estimation.

Q2 / W2: ablations and hyperparameters:

On averaging. Lemma 17 shows analytically what averaging contributes. Without it, the policy is a single softmax over the current predictions, softmax(−ηm(Bm−1)f~m)\mathrm{softmax}(-\eta_m (B_m-1) \tilde f_m). This is Boltzmann exploration, whose limitations are known in multi-armed bandits (Cesa-Bianchi et al., 2017). Here, the probability of an action falls exponentially in its predicted gap, so the linear bound (27) fails once batches are long. Averaging adds the early iterates, which keep mass on every action and give (27) for every batch. We will add the last-iterate variant as an empirical ablation in Appendix H.

On recovery from inaccurate predictions. The privacy sweep partly tests this: smaller ε\varepsilon makes every predictor less accurate, and our algorithms degrade gracefully (Figures 1, 4, 5).

On hyperparameters. Our comparison covers 100 datasets, five privacy regimes, and 10 seeds (4M runs), with a consistent ordering of algorithms in every private regime (Figure 2). As in Bietti et al. (2021) and Foster & Krishnamurthy (2021), configurations are selected per dataset in hindsight, here on 10 seeds rather than one. To check that selection does not drive the comparison within datasets, we re-ran every selected configuration on OpenML 1489 (5,404 rounds) with 1,000 new seeds (table in the next comment). The loss changes by at most 0.006 and by 0.002 on average, and the ordering of algorithms remains consistent. The revision will report this extended evaluation for all 100 datasets, together with a fixed-configuration comparison evaluated on held-out datasets.

Q3: numerical optimization and the privacy budget: Solving the perturbed objective numerically is the standard practice, including Chaudhuri et al. (2011), whose own experiments use L-BFGS. Our tolerances (gtol 10−810^{-8}, ftol 10−1210^{-12}) make the solution exact to numerical precision. Footnote 3 already states that the guarantee is for the exact minimizer, and we will add the tolerances there. The reported (ε,δ)(\varepsilon,\delta) covers one fixed hyperparameter configuration: selection is done in hindsight, equally for all methods, and is not charged to the budget, as is common in empirical DP comparisons.

AuthorsOpenReview ↗

Supplement to Q2 in the rebuttal

OpenML 1489. Each cell shows reported (10 seeds) / re-run (1,000 seeds) mean final PV loss. NP = non-private. δ=10−5\delta = 10^{-5} in the private rows.

PrivacyVanillaPOBonusPOSquareCBFastCBLinUCBRegCBAdaCBFull info
NP.254/.253.237/.237.254/.252.253/.253.255/.252.254/.252.253/.252.243/.244
ε=8\varepsilon=8.260/.257.250/.250.259/.257.259/.257.268/.262.268/.265.267/.263.250/.250
ε=4\varepsilon=4.265/.263.257/.255.266/.263.267/.263.274/.277.276/.274.274/.274.257/.256
ε=2\varepsilon=2.275/.273.268/.263.274/.273.274/.274.297/.298.292/.296.290/.296.264/.266
ε=1\varepsilon=1.297/.299.284/.278.297/.298.297/.298.300/.306.302/.306.302/.305.273/.277

We hope our responses address your concerns. If so, we would be grateful if you would consider raising your score.

Reviewer_rjzSOpenReview ↗

answer

Thank you for the response and the additional experiments.

  • The comparison with FALCON+ and He and Zhou (2025) helps clarify the contribution. I continue to find the result on exploration without explicit bonuses the most interesting part of the paper.

  • The results with 1,000 new seeds are reassuring, though they cover only one dataset. The promised averaging ablation and evaluation with independently selected hyperparameters would indeed help address the remaining experimental questions.

  • I also found the exchange with Reviewer KZSn useful. The feature-normalization question seems answered? However, the regret guarantee still does not cover the replay BonusPO used in the experiments, and the concerns about the uncertainty radii remain partly open.

  • The scope of the privacy budget is now clear: it covers a fixed configuration, excluding model selection. The tighter solver tolerances are useful to report, but the privacy guarantee for the approximate solution remains a separate question, which I believe would be nice to address in some future work.

We are glad that you found the vanilla PO result the most interesting part of the paper, as this is our main contribution. To our knowledge, it is the first proof that vanilla PO provides sufficient exploration to achieve near-optimal regret in stochastic contextual bandits under realizability, without explicit exploration bonuses. We believe this offers an important insight for both the contextual bandit and reinforcement learning communities.

The paper also provides, to our knowledge, the first generic oracle-based cumulative-regret guarantee for private stochastic contextual bandits with general function classes. We view the connection between offline regression and private bandit learning as an important conceptual contribution, bringing together ideas from the contextual bandit and privacy literatures. Our comprehensive experiments complement these results by comparing a broad range of methods, with and without privacy, and demonstrating the practical effectiveness of policy optimization.

We also appreciate your suggestions for strengthening the experiments. The revision will extend the 1,000-seed re-evaluation to all 100 datasets and include a fixed-configuration comparison on held-out datasets. Regarding the BonusPO implementation and the choice of uncertainty radii, we will explain the motivation for these design choices more clearly in the revision, incorporating the clarifications from our response to Reviewer KZSn.

We hope these clarifications and additional evaluations address your concerns. We would be grateful if you would consider the theoretical contributions, together with these additions, in your final assessment.

Reviewer_KZSnOpenReview ↗
Rating
4(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
3(+1)
Read review
Paper summary

This paper studies exponential-weights policy optimization (PO) with an offline regression oracle in realizable stochastic contextual bandits over AA actions and TT rounds. In the non-private round-by-round setting (Algorithm 1), Theorem 3 establishes O~(ATlog⁡(∣F∣/δ))\widetilde{O}(\sqrt{AT\log(|\mathcal{F}|/\delta)}) regret for a finite realizable class using least-squares regression, without explicit exploration bonuses. The explicit bound includes a (1+log⁡(AT))3/2(1+\log(AT))^{3/2} factor. On a doubling epoch schedule, the paper introduces a batched variant (Algorithm 2, Theorem 4) that fits the oracle on the preceding batch and constructs a new deployed policy by averaging BmB_m auxiliary exponential-weight distributions, starting from uniform and using that single predictor. Appendix G gives a batched bonus-augmented variant (BonusPO, Algorithm 3, Theorem 22). Replacing each regression fit with a private oracle yields privacy for the released predictors and policy maps, with no composition factor in the number of epochs, under the stated single-use batching and release convention (Theorem 7, Corollary 8). The experiments compare batched implementations of VanillaPO, BonusPO, SquareCB, FastCB, LinUCB, RegCB, and AdaCB across 100 OpenML datasets in non-private and private regimes.

Critical strengths
  • The proof of Theorem 3 (via Lemmas 13–15) is mathematically rigorous and establishes a nontrivial theoretical result: in realizable stochastic contextual bandits, standard multiplicative-weights policy updates driven by per-round regression fits maintain sufficient action coverage without explicit exploration bonuses or inverse-gap weighting. The inductive historical-coverage argument (Lemma 15) and the importance-weighted Cauchy–Schwarz transfer across rounds (Lemma 14) are clean and genuinely analyze sequential policy optimization.
  • The deployed policy changes at epoch boundaries, while its auxiliary updates restart from uniform rather than continue multiplicatively from the preceding epoch's policy. Lemmas 17 and 23 establish the inverse-probability and predicted-regret bounds needed for the subsequent regression-oracle analysis. The relationship to the framework of Simchi-Levi & Xu (2022) is acknowledged in Section 4 and Appendix E.4. The single-use batch construction also gives a direct privacy argument for the released transcript through a private fit followed by post-processing.
Critical weaknesses
  • Structural disconnect between the analyzed batched algorithms (Algorithms 2 and 3), sequential policy optimization, and the empirically evaluated BonusPO (Sections 4 and 6; Appendices E, G, and H.3).

    • In Algorithms 2 and 3, the policy is not updated across epochs. At the start of each epoch mm, both algorithms discard the previous epoch's policy, reset to the uniform distribution 1/A1/A, and average BmB_m synthetic updates driven by the single static predictor f~m\widetilde{f}_m fitted on batch m−1m-1. Mathematically, this within-epoch restart-and-average operation is a static functional of f~m\widetilde{f}_m designed to satisfy the per-epoch inverse-probability and predicted-regret inequalities πm(c,a)−1≤C0(A+γmdm(c,a))\pi_m(c,a)^{-1} \le C_0(A + \gamma_m d_m(c,a)) and R^m(πm)≤O~(A/γm)\widehat{\mathcal{R}}_m(\pi_m) \le \widetilde{O}(A/\gamma_m) (Lemmas 17 and 23). Once those two inequalities hold, the remainder of the batched regret proof (Lemmas 18-20 in Appendix E and Theorem 22 in Appendix G) directly follows the epoch-inductive regression-oracle framework of Simchi-Levi & Xu (2022, Appendix A.3-A.5, Lemmas 5-8). Framing these within-epoch static mixtures as showing that batched policy optimization and batched bonus PO achieve optimal regret overstates what changes relative to FALCON+.
    • More consequentially, the BonusPO algorithm evaluated in all experiments (Section 6 and Appendix H.3, lines 2062-2073) is a different algorithm from the BonusPO analyzed in Theorem 22 (Algorithm 3, Appendix G). Theorem 22 relies on subtracting the minimum predicted loss min⁡bf~m(c,b)\min_b \widetilde{f}_m(c,b) before applying the bonus and clipping (explicitly noted on p. 32, lines 1696-1699 as required so the predicted best action has adjusted loss zero), resets probability-mass counts Nm,0(c,a)=0N_{m,0}(c,a) = 0 at each evaluation on a single predictor f~m\widetilde{f}_m, and deploys the uniform average of the BmB_m auxiliary iterates. The experimental implementation instead replays updates across all past batch predictors f^j+1\widehat{f}_{j+1} (j=1,…,m−1j=1,\dots,m-1) with step size ηBj\eta B_j, omits loss centering before clipping, and deploys the final iterate qm−1q_{m-1}. As a result, the paper's best-performing empirical method is not covered by Theorem 22, and the algorithm proved in Theorem 22 is never empirically tested.
  • Unprotected matrix indefiniteness, estimator-radius mismatch, and uncertified numerical privacy in the experimental baselines and oracles (Appendix H.2-H.3).

    • To construct private baselines for LinUCB, RegCB, and AdaCB, Appendix H.2 (p. 38) defines the uncertainty proxy rj(c,a)=max⁡{ϕ(c,a)⊤(∑i=1jG~i+I)−1ϕ(c,a),0}r_j(c,a) = \sqrt{\max\{\phi(c,a)^\top (\sum_{i=1}^j \widetilde{G}_i + I)^{-1}\phi(c,a), 0\}}, where G~i=Gi+Ei\widetilde{G}_i = G_i + E_i is the batch Gram matrix perturbed by symmetric Gaussian noise EiE_i. Because the diagonal shift is fixed at +I+I rather than scaled with the noise spectral norm ∥∑i=1jEi∥op\|\sum_{i=1}^j E_i\|_{\mathrm{op}}, the matrix Mj=∑i=1jG~i+IM_j = \sum_{i=1}^j \widetilde{G}_i + I is not guaranteed to be positive definite; negative eigenvalues cause quadratic forms to be clipped to zero, while small positive eigenvalues can inflate Mj−1M_j^{-1}. Furthermore, the linear predictor θ^j+1lin=(G~j+njλI)−1q~j\widehat{\theta}_{j+1}^{\mathrm{lin}} = (\widetilde{G}_j + n_j \lambda I)^{-1}\widetilde{q}_j (Eq. 54) is fitted only on the single batch jj with regularization njλIn_j \lambda I, whereas rj(c,a)r_j(c,a) sums G~i\widetilde{G}_i across all batches 1,…,j1,\dots,j with unit regularization II. This mismatch between the single-batch estimator and the unshifted cumulative radius undermines the empirical claim that confidence-radius methods are inherently less resilient to privacy noise than policy optimization.
    • For the private logistic oracle (Eq. 55 and Footnote 3), the pure εP\varepsilon_P-DP proof of objective perturbation (Chaudhuri et al., 2011, Theorem 9) requires exact stationarity ∇Ljlog(θ^)+κjθ^+bj/nj=0\nabla L_j^{\mathrm{log}}(\widehat{\theta}) + \kappa_j \widehat{\theta} + b_j/n_j = 0. Because L-BFGS accesses the raw batch data and terminates with nonzero gradient residuals, the exact-minimizer theorem does not automatically certify the privacy of the implemented logistic oracle.
Questions for authors
  1. On horizons where Algorithm 3 is computationally feasible, how does its centered, averaged construction compare with the historical-replay implementation? Can suitable inverse-probability and predicted-regret bounds be established for the replay rule qj(a)∝qj−1(a)exp⁡(−ηBjf~j,a)q_j(a)\propto q_{j-1}(a)\exp(-\eta B_j\widetilde{f}_{j,a}), which uses one bonus-adjusted update per preceding batch and deploys the final iterate?
  2. Across the private quadratic-oracle runs with ε∈{1,2,4,8}\varepsilon\in\{1,2,4,8\}, how often do ∑i=1jG~i+I\sum_{i=1}^j\widetilde{G}_i+I and G~j+njλI\widetilde{G}_j+n_j\lambda I have negative or near-zero eigenvalues? How do the radius-based methods perform when the estimator and radius use matching statistics and regularization, with a confidence bound accounting for privacy noise and regularization bias?
  3. Line 1948 normalizes cˉ=c/max⁡{1,∥c∥2}\bar{c} = c/\max\{1, \|c\|_2\}, while Footnote 2 states that ∥ϕ(c,a)∥2≤1\|\phi(c,a)\|_2 \le 1 applies to the full feature vector including the suppressed constant bias coordinate. Could you clarify how the bias coordinate is scaled relative to cc in the code so that ∥ϕ(c,a)∥2≤1\|\phi(c,a)\|_2 \le 1 holds with the stated sensitivities ΔG\Delta_G and Δq\Delta_q?
3 comments
AuthorsOpenReview ↗

Rebuttal (1/2): W1 and W2

Thank you for the detailed review. Our response is split into two comments: W1 and W2 here, Q1-Q3 in the next.

W1: Batched algorithms and the BonusPO implementation.

Batching and privacy extensions relative to FALCON+ (Simchi-Levi and Xu, 2022): Indeed, we build on FALCON+’s epoch-based offline regression framework, including fitting on the preceding batch and comparing predicted regret with true regret. We do not claim these ingredients as new. The new ingredient in our batching extension is the policy construction and its analysis. FALCON+ uses inverse-gap sampling, whereas our policy averages exponential updates driven by a fixed predictor. We prove that this average simultaneously provides sufficient exploration (its inverse action probabilities grow at most linearly with the predicted loss gaps) and small predicted regret. These properties allow the regression-based analysis to establish near-optimal regret for batched vanilla PO with O(log⁡T)O(\log T) oracle calls. The efficient implementation allows exact sampling using only AA predictor evaluations and O(A)O(A) additional arithmetic per round.

We view the connection between oracle-based contextual bandit learning and differential privacy as an important conceptual contribution. It yields private algorithms that access general realizable function classes only through a private offline regression oracle, with cumulative-regret guarantees expressed in terms of the oracle’s accuracy. To our knowledge, this is the first such generic oracle-based regret guarantee for private stochastic contextual bandits. Our comprehensive experimental evaluation complements these guarantees by highlighting the practical benefits of this approach through comparisons with established contextual-bandit baselines.

Historical-replay implementation of BonusPO: Algorithm 3 needs O(T2)O(T^2) updates per run, so the experiments use an O(Tlog⁡T)O(T \log T) historical-replay approximation of it (Section 6). Evaluating an efficient variant of an analyzed algorithm is standard practice when the analyzed one is too costly to run at scale (e.g., Algorithm 1 in Agarwal et al., 2014). Our implementation keeps the bonus mechanism of Levy & Mansour (2026) and, since its policy is still a function of the released private predictors, the same privacy guarantee. In our comparisons, it is the best bandit method and often comes close to the full-information reference.

W2: Private baselines.

To make the algorithms comparable, we apply the same batching and the same private regression oracles to all of them. This isolates the effect of the policy rule from the choice of privacy mechanism. With the quadratic oracle, the radius reuses the Gram matrices the oracle already releases, at no extra privacy cost. Existing private versions of LinUCB rely on different privacy models and would not be comparable on these terms, and, to our knowledge, RegCB and AdaCB have no private versions at all. The radius here is an uncertainty proxy with scale β\beta tuned per dataset and privacy level.

On indefiniteness. We do not require the radius matrix ∑iGi+I+∑iEi\sum_i G_i + I + \sum_i E_i to be positive definite. With continuous noise, the matrix is invertible with probability one, and max⁡(⋅,0)\max(\cdot, 0) clips negative quadratic forms to zero. Moreover, in our stochastic setting the radius is evaluated at contexts drawn from the same distribution as the data, so the data term ∑iGi=∑iXi⊤Xi\sum_i G_i = \sum_i X_i^{\top} X_i grows linearly along the queried directions, while the noise term ∑iEi\sum_i E_i grows only logarithmically (O(log⁡T)O(\log T) batches).

On numerical optimization. Solving the perturbed objective numerically is the standard practice, including Chaudhuri et al. (2011), whose own experiments use L-BFGS. We solve with L-BFGS at tight tolerances (gtol 10−810^{-8}, ftol 10−1210^{-12}). Footnote 3 already states that the guarantee is for the exact minimizer, and we will add the tolerances there.

AuthorsOpenReview ↗

Rebuttal (2/2): Q1, Q2, and Q3

Q1: Algorithm 3 and historical replay implementation.

Short-horizon comparison. We compared exact Algorithm 3 with the historical-replay implementation on a 128-round prefix of OpenML 1462 (two actions), averaging over 100 seeds. Replay attains lower mean final PV loss at every privacy level except ε=1\varepsilon = 1, where both approach the chance level of 0.5 and Algorithm 3 is slightly better.

PrivacyBonusPO (replay)Algorithm 3
Non-private0.1220.297
80.3010.424
40.3770.447
20.4500.492
10.4970.487

Potential extension. Two ingredients of Lemma 23 carry over to the replay rule: unnormalized weights never increase, and an action that has not yet been penalized keeps probability at least 1/A1/A. The quantity they involve, however, is the cumulative mass ∑jBjqj−1(c,a)\sum_j B_j q_{j-1}(c,a), i.e., the time-averaged deployed policy, not the current iterate. This is the coverage notion of Theorem 3, not of Lemma 19, and using it would require fitting on all past batches as in Algorithm 1. We believe regret guarantees can be established along these lines for a replay variant that fits on all past batches. We leave this analysis to future work, as the paper focuses on theoretical guarantees for vanilla PO and a broad empirical comparison of oracle-based algorithms.

Q2: Indefinite matrices and matched LinUCB.

Eigenvalue statistics. As discussed in W2, we do not require these matrices to be positive definite. We measured how often this occurs for LinUCB with the quadratic oracle on OpenML 1489 (5,404 rounds, 1,000 seeds, selected hyperparameters); percentages below are listed for ε=8,4,2,1\varepsilon = 8, 4, 2, 1 in that order. The radius matrix is indefinite in 12/26/52/87% of rounds and the estimator matrix in 47/20/75/17%. Yet the chosen action’s radius is zero in only 3/7/14/22% of rounds, so it stays positive in over two thirds of the indefinite rounds. Near-zero eigenvalues (magnitude at most 0.010.01) occur in only 0.07/0.04/0.10/0.04% of rounds for the radius matrix and 0.85/0.14/0.21/0.02% for the estimator matrix, so severe inflation of the inverse is rare.

Matching statistics and regularization. We ran the requested implementation of LinUCB with quadratic oracle on OpenML 1462 and 1560, averaging over 1000 seeds. We used ∑i≤j(G~i+niλI)\sum_{i\le j} (\tilde G_i + n_i\lambda I) for both the estimator and the radius matrix. The effect is dataset-dependent: on 1462 the matched LinUCB improves under privacy (0.335→0.3180.335 \to 0.318 at ε=1\varepsilon = 1); on 1560 it is worse (0.437→0.4900.437 \to 0.490 at ε=1\varepsilon = 1). BonusPO has lower mean loss than either LinUCB version on both datasets under privacy. We are happy to add this variant as a hyperparameter option.

Q3: Bias coordinate and feature scaling.

The code sets z=(1,cˉ)/2z = (1, \bar c)/\sqrt{2} with cˉ=c/max⁡(1,∥c∥2)\bar c = c/\max(1, \Vert c\Vert_2), so ∥ϕ(c,a)∥22=(1+∥cˉ∥22)/2≤1\Vert\phi(c,a)\Vert_2^2 = (1+\Vert\bar c\Vert_2^2)/2 \le 1 and the stated sensitivities hold. It uses the tighter Δq=2\Delta_q=\sqrt{2}, valid because within-block inner products equal (1+cˉ⋅cˉ′)/2≥0(1+\bar c\cdot\bar c')/2 \ge 0, so ∥xy−x′y′∥22≤2\Vert xy - x'y'\Vert_2^2 \le 2. Footnote 2 already states that the bound covers the bias coordinate, and we will elaborate on it.

Thank you again for the careful reading. We hope the clarifications and new experiments resolve the points you raised, and that you will consider revisiting your score.

Thank you for addressing these subtleties, I have raised my score to 4.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.