{"id":"d90a0dde-6ec5-44f4-9e6c-a2cf18029b86","arxiv_id":"2505.05613","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"For epsilon-global-DP Bernoulli bandits, the paper proves a tighter lower bound and matching upper bounds (up to a factor alpha that can approach 1) using a new quantity d_epsilon and a new DP-Chernoff concentration inequality.","lead":"This paper tightens the regret bounds for differentially private Bernoulli bandits, introducing a new privacy-aware complexity measure that interpolates between KL divergence and total variation distance. The authors give two algorithms whose regret matches the new lower bound up to a constant arbitrarily close to 1.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Post-convergence upper-bound proof misapplies Corollary 20: Eq. (45) uses d_epsilon(mu_i + delta'/epsilon, mu_star) where the concentration lemma requires the true mean mu_i.","rationale":"The reader's conditional verdict is appropriate. The central claim depends on the concentration lemma, and the reader flagged Lemma 19/Proposition 7 as the load-bearing premise. My check found a concrete misapplication in the regret analysis rather than in the concentration lemma itself: Eq. (45) uses mu_star as the second argument of d_epsilon when bounding a tail of arm i's private mean. This is not a matter of taste; the displayed bound is not implied by Corollary 20 and can be exponentially too small. However, the correction is local: replacing mu_star by mu_i gives a positive exponent, and because the batch sizes grow geometrically, the resulting infinite sum over phases is O(1) for each fixed delta'. The final limit delta' -> 0 is unchanged. I also considered whether Lemma 19's proof has a separate sign issue in the integration-by-parts step around Eq. (22); the step appears repairable as an upper bound, but it should be checked when the appendix is revised. For these reasons I would not change the reader's CONDITIONAL verdict: the paper should not be accepted until the appendices are corrected, but the claimed result is plausibly salvageable and the concern does not amount to a rejection. The numerical experiments lacking error bars/code are a secondary issue and do not affect the verdict.","tokens_in":37416,"tokens_out":37968,"duration_ms":402107,"concrete_test":"Re-derive Eq. (45) by applying Corollary 20 with mu = mu_i instead of mu_star. Concretely, replace d_epsilon(mu_i+delta'/epsilon, mu_star) in the exponent and in Lambda by d_epsilon(mu_i+delta'/epsilon, mu_i), then check whether sum_{m>=m*} B_{m+1} exp(-nm (d_epsilon(mu_i+delta'/epsilon, mu_i)-a')) is bounded by a constant independent of T for each fixed delta' < epsilon(mu_star-mu_i), and whether the final delta'->0 limit still yields the o(log T) term. Also verify the numerical ordering d_epsilon(0.11,0.1) < d_epsilon(0.11,0.9) to confirm the displayed inequality in the current text is not a consequence of Corollary 20.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The matching upper bound Theorem 9 rests on Proposition 7, and the step that converts the post-convergence bad event into a probability estimate is not a valid application of that proposition. In the proof of Theorem 25 (Appendix F), after showing that the event nm(d_epsilon([mu_tilde_{i,m}]_0^1, mu_star)-delta') <= log T implies mu_tilde_{i,m} >= mu_i + delta'/epsilon, the paper bounds Pr[mu_tilde_{i,m} >= mu_i + delta'/epsilon] by A exp(-nm (d_epsilon(mu_i+delta'/epsilon, mu_star)-a')) and cites Corollary 20. Corollary 20 applied to arm i's own samples gives the exponent d_epsilon(mu_i+delta'/epsilon, mu_i), not d_epsilon(., mu_star). These two quantities are not ordered in the needed direction: for mu_i=0.1, mu_star=0.9, epsilon=1, delta'=0.01, d_epsilon(0.11,0.1) is about 5e-4 while d_epsilon(0.11,0.9) is about 0.75, so the displayed bound is exponentially smaller than the concentration lemma can justify. The error appears again in Lambda just below Eq. (45). The theorem may still be true, because the corrected positive exponent d_epsilon(mu_i+delta'/epsilon, mu_i) makes the geometric batch sum converge to an O_delta'(1) term, but the proof as written does not establish the claimed upper bound.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies regret minimization in stochastic Bernoulli bandits under ε-global differential privacy. It introduces a new quantity d_ε (Eq. (6)) that interpolates between KL divergence and total variation, proves an asymptotic regret lower bound (Theorem 5) in terms of d_ε, and proposes two algorithms, DP-IMED and DP-KLUCB, whose regret is claimed to match this lower bound up to a factor α>1 arbitrarily close to 1 (Theorem 9). The main technical novelty is a concentration inequality for sums of Bernoulli variables with added Laplace noise (Proposition 7/Lemma 19). The paper also claims to refute the conjecture that forgetting past rewards is necessary for optimal DP bandits, and reports experiments on several Bernoulli environments.","tokens_in":37687,"tokens_out":15595,"duration_ms":142486,"significance":"If fully established, the results would close the constant-factor gap for Bernoulli bandits under pure global DP, a question posed by Azize and Basu (2022). The lower bound with d_ε is a clear conceptual improvement over the existing min{kl, εΔ} bound, and the coupled concentration inequality for noise-plus-data tails is a useful standalone contribution that may benefit other DP analyses. The proof of the lower bound is coherent, and the central ideas of the upper bound are plausible. However, the upper-bound proof currently contains a misapplication of the concentration lemma at a load-bearing step, so the matching claim is not yet rigorously supported.","major_comments":[{"comment":"The post-convergence analysis of Theorem 25 applies Corollary 20 with the exponent d_ε(μ_i + δ'/ε, μ_⋆), but Corollary 20 applied to the samples of arm i yields the exponent d_ε(μ_i + δ'/ε, μ_i), not d_ε(·, μ_⋆). These two quantities are not ordered in the needed direction: for μ_i=0.1, μ_⋆=0.9, ε=1, δ'=0.01, d_ε(0.11,0.1) is about 5e-4 while d_ε(0.11,0.9) is about 0.75, so the displayed probability bound in Eq. (45) is exponentially smaller than the concentration lemma can justify. The same misuse appears in the definition of Λ immediately below Eq. (45) and is carried into the DP-KLUCB proof in Theorem 26 through its reference to Eq. (42). The theorem may still be true, because the corrected exponent d_ε(μ_i + δ'/ε, μ_i) is positive and makes the geometric batch sum converge to an O_{δ'}(1) term, but the proof as written does not establish the claimed upper bound.","section":"Appendix F, proof of Theorem 25 (Eq. (45))"}],"minor_comments":[{"comment":"The word 'georemetrically' should be 'geometrically'; similar typos appear in the appendices (e.g., 'tet', stray arrows in displayed equations).","section":"Section 4, comments after Theorem 9"},{"comment":"The equality ∫_{x-nμ}^{∞} F_m(z)(-P̄'(x-z)) dz = F_m(x-nμ) P̄(nμ) is not correct as written; with the natural convention P̄(s)=1 for s<nμ the integral on the left is zero, and the displayed bound remains valid only as an inequality. The final upper bound is unaffected, but the line should be corrected.","section":"Appendix D, proof of Lemma 19"},{"comment":"The constant A_ε is written with (m+1) in the exponent while Lemma 19 has m; since the algorithms use one extra Laplace noise per phase, the relationship between m in the lemma and the phase index in the regret proofs should be stated explicitly.","section":"Appendix D, proof of Corollary 20"},{"comment":"The argument is presented for two arms; the standard K-armed extension should be spelled out, since the WLOG statement is not literally without loss of generality for K>2.","section":"Section 3, proof of Theorem 5"},{"comment":"The second panel is said to be run with b=L, which appears to be a typo for b=R.","section":"Appendix B, Figure 2 caption"}],"recommendation":"major_revision","confidential_remarks":"The paper addresses a well-known open problem in DP bandits and the lower bound part is convincing. The main risk is the gap in the upper-bound proof identified in my report; it seems fixable by replacing d_ε(μ_i+δ'/ε, μ_⋆) with d_ε(μ_i+δ'/ε, μ_i), but the authors should also double-check the concentration lemma's proof details. The experimental section is useful but not decisive."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things before anything else. The lower bound is the real contribution: the double change-of-environment argument, coupling group privacy with a Lai-Robbins KL transport, is genuinely new, and the quantity d_epsilon is a clean interpolation between KL and TV that I expect people will reuse. The DP-Chernoff bound, coupling Bernoulli sums with Laplace noise instead of treating them separately, is also a genuinely useful tool. The algorithms are interesting too: no-forgetting DP-KLUCB and DP-IMED, with batched arm-dependent phases, directly address the open conjecture about forgetting. The privacy analysis is straightforward and, as far as I can tell, correct. Good paper to have in the world, and the lower bound alone may carry it.\n\nBut the upper-bound proof has a real bug, and the stress-test note is right. In the post-convergence part of Theorem 25, the paper bounds Pr[mu_tilde_{i,m} >= mu_i + delta'/epsilon] using Corollary 20 with exponent d_epsilon(mu_i + delta'/epsilon, mu_star). Corollary 20 applied to arm i's own samples gives exponent d_epsilon(mu_i + delta'/epsilon, mu_i), not d_epsilon(., mu_star). These are not interchangeable: when mu_star is far from mu_i, the displayed exponent is much larger, so the bound is exponentially stronger than the lemma justifies. The same issue appears in the Lambda term just below Eq. (45). This is not a typo; it is load-bearing for the claimed constant-matching upper bound.\n\nThat said, I do not think this is necessarily fatal. The corrected exponent d_epsilon(mu_i + delta'/epsilon, mu_i) is of order delta' for small delta', so the geometric batch sum should still converge to an O_{delta'}(1) term, which is o(log T). The theorem may survive with a repaired proof, but the repair has to be written down. As it stands, the proof does not establish Theorem 9. I would also note the minor stuff: experiments have no error bars and no code, and the appendix has typos, but those are secondary.\n\nMy honest score: the lower bound is solid, the upper bound is conditional. This paper deserves a serious referee, but the referee should be asked to check Lemma 19 and its application in Appendix F carefully. If the correction goes through, I would be happy to see it accepted; if not, major revision.","headline":"The lower bound and d_epsilon are genuinely new and likely correct, but the proof of the matching upper bound has a real misapplication of the paper's own concentration lemma at Eq. (45), so Theorem 9 is not established as written.","tokens_in":700,"tokens_out":861,"would_cite":true,"duration_ms":51783,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62L05","68T05"],"pacs":[],"model":"deepseek-v4-flash","headline":"For Bernoulli bandits under global differential privacy, the optimal asymptotic regret is governed by one divergence $d_\\epsilon$ that interpolates KL and total variation.","keywords":["Bernoulli bandits","global differential privacy","regret lower bound","Laplace mechanism","KL divergence","total variation distance","concentration inequality","multi-armed bandits"],"falsifier":"Simulate $\\tilde S_{n,m}/n$ for fixed $\\mu=0.5$, $\\epsilon=1$, $m=1$ and $m=\\sqrt{n}$, estimate the log-probability of the event $\\tilde S_{n,m}/n>0.75$, and check whether the rate matches $d_\\epsilon(0.75,0.5)$; a systematic gap would falsify Proposition 7. Alternatively, run DP-IMED on a two-armed environment with means $(0.5,0.9)$ for $T=10^7$, compute $\\mathrm{Reg}_T/\\log T$, and compare with $\\Delta_a/d_\\epsilon(\\mu_a,0.9)$; a repeated value below the lower bound would indicate either the lower-bound proof or the claimed privacy guarantee is wrong.","tokens_in":37169,"feed_emoji":"🔒","tokens_out":6477,"duration_ms":64277,"temperature":0.7,"pith_summary":"The paper claims to settle the constant in the regret of Bernoulli multi-armed bandits under global differential privacy: the best possible regret per $\\log T$ is the sum over suboptimal arms of $\\Delta_a / d_\\epsilon(\\mu_a, \\mu_\\star)$, where $d_\\epsilon$ is a new divergence that reduces to KL when privacy is loose and to $\\epsilon$ times total variation when privacy is tight. It proves a matching lower bound and gives two algorithms, DP-IMED and DP-KLUCB, whose regret is at most $\\alpha$ times that sum, with $\\alpha>1$ arbitrarily close to 1. The consequence is a complete privacy-utility tradeoff for this setting. The paper also refutes the earlier conjecture that an optimal private bandit algorithm must forget old rewards.","feed_headline":"One divergence fixes the regret of private bandits","feed_subtitle":"DP-IMED and DP-KLUCB match the regret lower bound up to a factor arbitrarily close to 1.","key_machinery":"The load-bearing object is a private Chernoff bound: for $\\tilde S_{n,m}=\\sum_{i=1}^n X_i+\\sum_{j=1}^m Y_j$ with $X_i\\sim\\mathrm{Ber}(\\mu)$ and $Y_j\\sim\\mathrm{Lap}(1/\\epsilon)$, whenever $m/n\\to 0$ the tail satisfies $\\Pr[\\tilde S_{n,m}/n\\le x]\\le A_a e^{-n(d_\\epsilon(x,\\mu)-a)}$ (and symmetrically for upper tails). This couples the Laplace noise and the Bernoulli data in one exponent rather than bounding them separately, which is what lets the algorithms accumulate noisy sums across phases without forgetting. For the lower bound, the key mechanism is a \"double change of environment\": a coupled-history argument that pays one $\\epsilon\\cdot\\mathrm{TV}$ term for switching between neighbouring reward lists via group privacy and one KL term for the classical Lai-Robbins change of measure, with the optimization over the intermediate environment producing exactly $d_\\epsilon$.","core_discovery":"The central claim is that for any consistent $\\epsilon$-global DP policy on Bernoulli bandits, $\\liminf_{T\\to\\infty} \\mathrm{Reg}_T(\\pi,\\nu)/\\log T \\ge \\sum_{a:\\Delta_a>0} \\Delta_a / d_\\epsilon(\\mu_a,\\mu_\\star)$, and that DP-IMED and DP-KLUCB achieve the same expression multiplied by $\\alpha$, where $\\alpha>1$ can be chosen arbitrarily close to 1. The divergence is $d_\\epsilon(x,y)=\\inf_{z\\in[x\\wedge y,x\\vee y]}\\{\\epsilon|z-x|+\\mathrm{kl}(z,y)\\}$. It interpolates smoothly between the non-private KL complexity and an $\\epsilon$-scaled total-variation cost, and in the high-privacy limit $d_\\epsilon(\\mu_a,\\mu_\\star)\\sim \\epsilon\\Delta_a$. The upper bound relies on a new concentration inequality for sums of Bernoulli variables with Laplace noise, and the algorithms run in arm-dependent phases while retaining all past rewards—no forgetting is used.","pith_inferences":["The form of Proposition 7 suggests that any phase schedule with a sublinear number of batches, not only geometric schedules, should yield the same asymptotic constant; the paper itself notes polynomial batch sizes would also suffice.","One can read $d_\\epsilon$ as a minimal transport cost between arm means under a mixture of KL and TV, which may transfer to best-arm identification or other privacy models once the analogous concentration bound is established.","The equivalence between adaptive continual release and $\\epsilon$-global DP for pure DP, proved in the appendix, implies that interactive algorithms with adaptively chosen rewards inherit the same regret characterization.","Extending the private Chernoff bound to sub-Gaussian or exponential family rewards would likely carry constant-optimal regret bounds to those broader bandit classes with the same $d_\\epsilon$ exponent."],"forward_implications":["The constant-optimal regret for $\\epsilon$-global DP Bernoulli bandits is characterized by $d_\\epsilon$: no consistent policy can beat $\\Delta_a/d_\\epsilon(\\mu_a,\\mu_\\star)$ per suboptimal arm.","DP-IMED and DP-KLUCB attain this constant up to a factor $\\alpha$, which can be made as close to 1 as desired by choosing the geometric batch ratio.","Reward forgetting is not necessary for optimal private bandits; keeping past rewards costs only asymptotically negligible extra noise.","The transition between high and low privacy regimes is smooth: $d_\\epsilon$ equals the non-private KL above a threshold and tends to $\\epsilon\\Delta_a$ as $\\epsilon\\to0$.","The new concentration inequality for private means is stated in a form that can be applied beyond the two specific algorithms, supplying a general tool for DP bandit analysis."],"supporting_citations":[{"why":"Provides the previous lower bound and the AdaP-KLUCB baseline that Theorem 5 strictly improves and Theorem 9 matches.","marker":"Azize and Basu (2022)"},{"why":"Introduces DP-SE and the phase-based Laplace blueprint whose reward forgetting this paper removes.","marker":"Sajed and Sheffet (2019)"},{"why":"Conjectures that forgetting is necessary for optimal private bandits; the new algorithms refute this conjecture.","marker":"Hu et al. (2021)"},{"why":"Supplies the IMED algorithm and its regret proof skeleton, which DP-IMED adapts to the $d_\\epsilon$ index.","marker":"Honda and Takemura (2015)"},{"why":"Defines the classical KL lower bound and consistency notion that the private lower bound extends.","marker":"Lai and Robbins (1985)"},{"why":"Supplies the DP definitions, Laplace mechanism, post-processing, and group-privacy tools used throughout both bounds.","marker":"Dwork and Roth (2014)"}],"fun_headline_variants":["One divergence pins down private bandit regret","Private bandits: tight regret without forgetting","DP-IMED and DP-KLUCB hit the regret floor","A new DP Chernoff bound closes bandit gap","Private bandits: optimal regret up to any constant"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The upper-bound analysis rests on Proposition 7's claim that a private mean with $n$ Bernoulli draws and $m$ Laplace noises has tail exponent $d_\\epsilon$ whenever $m/n$ tends to 0; if that exponent is even slightly wrong, the constant $\\alpha$ matching with the lower bound would break.","fun_headline_variants_meta":{"raw":{"variants":["One divergence pins down private bandit regret","Private bandits: tight regret without forgetting","DP-IMED and DP-KLUCB hit the regret floor","A new DP Chernoff bound closes bandit gap","Private bandits: optimal regret up to any constant"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000623,"raw_usage":{"total_tokens":2948,"prompt_tokens":1069,"completion_tokens":1879,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":685,"completion_tokens_details":{"reasoning_tokens":1802}},"tokens_in":685,"tokens_out":1879,"duration_ms":14831,"temperature":1.0,"reasoning_tokens":1802,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T23:01:34.641135+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Simulate $\\tilde S_{n,m}/n$ for fixed $\\mu=0.5$, $\\epsilon=1$, $m=1$ and $m=\\sqrt{n}$, estimate the log-probability of the event $\\tilde S_{n,m}/n>0.75$, and check whether the rate matches $d_\\epsilon(0.75,0.5)$; a systematic gap would falsify Proposition 7. Alternatively, run DP-IMED on a two-armed environment with means $(0.5,0.9)$ for $T=10^7$, compute $\\mathrm{Reg}_T/\\log T$, and compare with $\\Delta_a/d_\\epsilon(\\mu_a,0.9)$; a repeated value below the lower bound would indicate either the lower-bound proof or the claimed privacy guarantee is wrong.","supporting_citations":[{"cited_title":"An optimal private stochastic- MAB algorithm based on optimal private stopping rule","cited_arxiv_id":null,"evidence_quote":"Introduces DP-SE and the phase-based Laplace blueprint whose reward forgetting this paper removes."},{"cited_title":"Non-asymptotic analysis of a new bandit algorithm for semi-bounded rewards","cited_arxiv_id":null,"evidence_quote":"Supplies the IMED algorithm and its regret proof skeleton, which DP-IMED adapts to the $d_\\epsilon$ index."},{"cited_title":"The algorithmic foundations of differential privacy","cited_arxiv_id":null,"evidence_quote":"Supplies the DP definitions, Laplace mechanism, post-processing, and group-privacy tools used throughout both bounds."}],"review_version":1}