{"id":"e5f308c9-ff31-4959-b2ac-2a7b86d78e88","arxiv_id":"2504.16371","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"Safe-Private Lin-UCB balances local differential privacy against safety in coupled linear bandits, with a provably unilaterally unimprovable privacy allocation for simplex safety sets under a regret budget.","lead":"This paper studies many agents whose private responses to chosen actions must be learned while a central coordinator keeps the expected responses inside a shared safety set. It proposes a safe, privacy-protected bandit algorithm and shows how to divide privacy noise among agents so that a regret bound stays within a fixed budget.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 3's constructed privacy vector can fail to exist: for agents with small c_m, the radicand is negative, so a* is not in R^M_+; the theorem as stated is not well-defined.","rationale":"I read Theorem 3 as the central claim: a concrete privacy vector that is unilaterally unimprovable for a given regret budget. The theorem's only construction is a*, and if the square root in its definition is not real, the claim has no object. This is not a matter of loose constants or asymptotic approximation; it is a well-definedness failure. The dependence on c_m means the failure is generic for simplex safe sets with heterogeneous constraint coefficients unless the budget U is large enough, and the paper neither states nor proves such a condition. The reader's designated weakest assumption was per-round versus full-sequence privacy, which is a different concern; however, the reader's rationale did mention that the constructed privacy vector may be infeasible for small constraint coefficients, so there is partial overlap. This issue is addressable by adding a feasibility condition or by modifying the construction, which supports keeping the paper conditional rather than accepting it as-is; I do not see a reason to move the verdict away from CONDITIONAL.","tokens_in":22887,"tokens_out":21548,"duration_ms":207500,"concrete_test":"Instantiate the radicand in Theorem 3 with R = sigma = 1, M = 2, c = (1, 0.1), so tilde_c = 1, and choose the problem constants so that the budget U gives tilde_r^2 = 10. Computing alpha*_2^2 = (1 + 10)(0.1)^2 - 1 = -0.89 shows the proposed vector is not real, so the theorem is not well-defined. To make the test fully constructive, invert the definition of tilde_r to find the corresponding U from the stated constants, then substitute back; if the radicand is negative, Theorem 3's assertion fails. Equivalently, derive the necessary condition tilde_r^2 > (R^2/sigma^2)(tilde_c^2 / min_m c_m^2 - 1) and check it against the paper's parameter ranges.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is that the closed-form vector in Theorem 3 satisfies a* in A*. The formula is alpha*_m = sqrt((R^2/sigma^2 + tilde_r^2)c_m^2/tilde_c^2 - R^2/sigma^2). This is a real number only if (R^2/sigma^2 + tilde_r^2)(c_m/tilde_c)^2 >= R^2/sigma^2 for every m. No such condition is stated in Theorem 3 or in the surrounding development. Since tilde_c = max_m c_m, every agent with c_m < tilde_c is at risk; for sufficiently small c_m the inequality fails for any finite tilde_r. For example, take R = sigma = 1, M = 2, c_1 = 1, c_2 = 0.1, tilde_c = 1, and choose U so that tilde_r^2 = 10; then alpha*_2^2 = (1 + 10)(0.1)^2 - 1 = -0.89, so alpha*_2 is not real and a* is not in R^M_+. If one instead clamps alpha*_m to 0, the proof's identities f(a*) = M and r(a*) = U no longer hold, so the unimprovability conclusion is unsupported. The theorem needs an explicit feasibility condition on U, or on tilde_r, relative to min_m c_m, or a modified construction.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper considers M linear stochastic bandit problems coupled by a global safety constraint of the form Θ_* X_t ∈ Y. Each agent adds Gaussian noise to its observed response before sharing it with a central coordinator, giving an (ε_m, δ)-LDP guarantee per released response. The coordinator runs a two-phase Safe-LUCB-style algorithm consisting of a pure-exploration phase and an optimism-based exploration-exploitation phase, with confidence radii inflated by the privacy noise. For polytopic safe sets, the paper gives a regret bound in terms of the sharpness of the transformed safe set Y′. It then specializes to simplex safe sets, derives a closed-form expression for the sharpness, and proposes a privacy vector a* that is claimed to be unilaterally unimprovable for a given asymptotic regret budget U, i.e. a* ∈ A*. Numerical experiments on a three-agent simplex compare regret for different privacy allocations.","tokens_in":23244,"tokens_out":8174,"duration_ms":76561,"significance":"If the results were fully correct, the paper would be a useful contribution: it formalizes a safety-privacy tradeoff in safe linear bandits, extends the sharpness framework of [5] to local differential privacy, and provides a concrete Pareto-style recommendation for allocating privacy levels across agents. The derivation of the sharpness of a simplex in Lemma 8 is self-contained, and the formulation of unilateral unimprovability in A* is a clear and meaningful notion. The paper also clearly identifies privacy noise as an additional contribution to the confidence radii β_{t,m}, which is the right structural mechanism. However, several load-bearing technical points are currently not supported as written: the printed regret bound in Theorem 2 has a scaling inconsistency, the constructive claim in Theorem 3 can fail to define a real privacy vector, and the proof of Theorem 3 contains an algebraic assertion that is false for the stated formula. These issues need to be resolved before the central claim can be accepted.","major_comments":[{"comment":"As printed, Theorem 2 evaluates Sharp∞_Y′ at 2√2K√(2ν + T′λ̌), whereas Lemma 5 defines the shrinkage parameter as l′ = 2√2K / √(2ν + T′λ̌) and uses it in that reciprocal form in Eq. (27) and Eq. (31). The printed form is dimensionally inconsistent and would make the second regret term grow like T′ instead of contributing the intended T^(2/3)-type rate. The theorem and the lemma must be reconciled, and the constants in the stated regret bound should be re-derived after the correction.","section":"Section IV, Theorem 2 and Lemma 5"},{"comment":"The vector a* defined in Theorem 3 need not exist in R_+^M. With α*_m = sqrt((R^2/σ^2 + r̃^2)c_m^2/c̃^2 - R^2/σ^2), the radicand can be negative whenever c_m is small relative to c̃. For example, take R = σ = 1, M = 2, c_1 = 1, c_2 = 0.1, c̃ = 1, and choose the budget U so that r̃^2 = 10; then (α*_2)^2 = 1.1·0.01 - 1 = -0.89, so α*_2 is not real. The theorem needs an explicit feasibility condition on U, or on r̃, relative to min_m c_m/c̃, or a modified construction.","section":"Section V, Theorem 3"},{"comment":"The proof of Theorem 3 claims that there exists a positive real B′ such that h_m(α*_m) = B′ for all m, where h_m(α_m) = c_m√(R^2 + α_m^2 σ^2). For the printed definition of α*, direct substitution gives h_m(α*_m) = c_m√(R^2 + r̃^2σ^2) c_m/c̃ = (c_m^2/c̃)√(R^2 + r̃^2σ^2), which depends on m unless all c_m are equal. Since both case arguments in the unimprovability proof rely on this property, the proof that r(a) > U for every a = a* + v with v ∈ R_+^M \\ {0} is not established.","section":"Appendix D6, proof of Theorem 3"},{"comment":"The paper states the LDP guarantee only for a single response at a single time step: Fact 1 says that at any single time t ∈ [T], Algorithm 1 is (ε_m, δ)-LDP. However, Algorithm 1 releases T perturbed responses per agent, and the coordinator's actions depend on the entire transcript. No composition bound is given for the full sequence. If the intended privacy guarantee is full-sequence LDP, the effective privacy parameter after T-fold composition would be different and would enter the confidence radii β_{t,m}, changing the tradeoff; if the intended guarantee is only per-round LDP, this limitation should be stated explicitly in the abstract and conclusion.","section":"Section III-A, Fact 1 and Appendix A"},{"comment":"The proof of Lemma 6 switches between H∞_Y and H∞_Y′ without justification. In Eq. (35) the bound is written as β_{T,m} H∞_Y, while Eq. (36) and the lemma statement use β_{T,m} max(H∞_Y′, 2). Since Y′ = BY with B = diag(1/β_{T,m}), the maximum shrinkages of Y and Y′ generally differ. This inconsistency affects the constant in the Term II bound and should be corrected.","section":"Appendix C, Lemma 6"}],"minor_comments":[{"comment":"The appendix labels a statement as 'Theorem 4 (Duplicate of Theorem 3)'; this duplicate numbering should be removed or the statement should be presented once.","section":"Appendix D6"},{"comment":"The notation x_{1:t} is defined but never used; the definition can be removed.","section":"Section I-B"},{"comment":"Figure 1 and Figure 3 appear to have essentially the same caption, although they are described differently in the text; the captions and the experimental protocol should be aligned.","section":"Section VI and Appendix E"},{"comment":"Algorithm 1 takes T′ as an input, while the later analysis sets T′ = max(t_h′, t_δ′, (2/λ̌)(β̃_T T)^(2/3)); the recommended choice of T′ should be stated before or within the algorithm description.","section":"Algorithm 1 and Eq. (66)"},{"comment":"There are scattered typographical issues in the displayed equations, including missing square-root bars and inconsistent use of p and √; a careful proofreading pass is needed.","section":"Overall"}],"recommendation":"major_revision","confidential_remarks":"The manuscript's central claim is interesting and the overall framework is plausible, but the printed version contains fixable yet load-bearing errors: the scaling error in Theorem 2, the nonexistence of α* for small c_m, and the false constant-B′ assertion in Appendix D6. These are not merely presentation issues. I do not see an unsurmountable obstacle to repair, so I recommend major revision rather than rejection, but the authors should be asked to provide a corrected statement and proof of Theorem 3, including a feasibility condition, and to reconcile the regret-bound constants."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know before you read it. First, the paper has a genuinely new and useful formulation: multiple linear bandits coupled by a global safety constraint, where each agent adds Gaussian LDP noise of a different level. Second, the central theorem (the unilaterally unimprovable privacy vector) is not well-defined as stated: for agents with small constraint coefficients c_m, the closed form for alpha*_m has a negative radicand, so the vector doesn't live in R^M_+. That is not a cosmetic issue; the proof of unimprovability relies on identities f(a*)=M and r(a*)=U, which break if you clamp the negative entries.\n\nWhat the paper does well. The generalization of Safe-LUCB to heterogeneous privacy levels is natural and the regret decomposition is clean. The exact sharpness computation for a simplex is a nice bit of geometry, and the observation that a symmetric simplex minimizes sharpness has some independent interest. The unilateral unimprovability concept is a good way to express the privacy-regret tradeoff, and the proof of Theorem 3 is self-contained once you grant the formula. The paper is honest about the per-round nature of the LDP claim (Fact 1). The experiments are too small to prove much, but they at least show the allocation rule behaving in the direction claimed.\n\nSoft spots, in order of seriousness. (1) Theorem 2 as printed evaluates the sharpness term at 2√2K√(2ν+T'λ̌); the proof of Lemma 5 and the units say it should be 2√2K/√(2ν+T'λ̌). If the printed version were the intended one, the bound would not have the claimed structure and would not yield the T^(2/3) rate. This is a typo, but it's in the main theorem. (2) Theorem 3 needs a feasibility condition. The radicand is negative whenever (R^2/σ^2 + \\tilde r^2)(c_m/\\tilde c)^2 < R^2/σ^2, which happens for any agent with sufficiently small c_m relative to the largest, unless U is large enough. For those parameter regimes the theorem is not even defined. The fix is straightforward—state a lower bound on U—but without it, the main contribution overreaches. (3) The LDP guarantee is per-round only. If the agents care about their whole trajectory, composition over T rounds changes the effective epsilon and the regret-privacy tradeoff; the paper doesn't address that. Minor: H∞(Y) and H∞(Y') get mixed up in the proof of Lemma 6, and the experiments lack error bars.\n\nOn the citation pattern: the paper leans on the same group's Safe-LUCB and sharpness papers, but it also extends them in a way that is mathematically self-contained. That's acceptable.\n\nBottom line: this is a solid conference-level paper for the safe/private bandit audience. The decomposition and the simplex sharpness results are worth having. It is not ready as-is because Theorem 3 is undefined in common parameter regimes and Theorem 2 has a wrong formula. Both are addressable. Send it to a serious referee; expect heavy but not impossible revision.","headline":"A useful and mostly sound extension of safe linear bandits to heterogeneous LDP, but the main unimprovability theorem is not well-defined for small constraint coefficients and the printed regret bound has a dimensional typo.","tokens_in":23765,"tokens_out":5467,"would_cite":true,"duration_ms":47234,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62L05","68T05","93E35"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper shows that when private agent responses are learned under a shared safety constraint with a simplex-shaped safe set, any fixed regret budget admits a privacy-allocation vector that no agent can individually improve upon.","keywords":["linear bandits","local differential privacy","safety constraints","regret bound","sharpness of constraint sets","simplex safe sets","unilaterally unimprovable privacy vector","upper confidence bound"],"falsifier":"Evaluate Lemma 13's formula at $a^* + v$ for a concrete simplex and a single positive coordinate of $v$: the unimprovability claim reduces to the arithmetic fact that $f(a) > M$ whenever the scaled radii $h_m(\\alpha_m)$ are not all equal, so a single evaluation that gave $r(a^* + v) \\le U$ would refute it. Separately, compose the per-round Gaussian mechanism over $T$ rounds under the algorithm's adaptive action rule (for instance by standard advanced composition) and compare the composed privacy parameter with the $\\varepsilon_m$ used in the confidence radii; a gap would show that the regret budget $U$ was calibrated with the wrong privacy parameter.","tokens_in":22684,"feed_emoji":"🔒","tokens_out":11670,"duration_ms":96268,"temperature":0.7,"pith_summary":"This paper asks how much privacy a group of agents can be granted when a central coordinator is learning their response models while a shared safety constraint must be satisfied at every round. Its central claim is that when the safe set is a simplex and a regret budget is fixed, there exists a privacy-allocation vector that is unilaterally unimprovable: no single agent can strengthen its own privacy guarantee without another agent weakening theirs or the regret budget being exceeded. The claim matters because it converts the vague privacy-versus-safety tension in multi-agent learning into a concrete design rule for distributing privacy among agents whose responses matter differently to the shared constraint. The route passes through a locally differentially private variant of a safe linear bandit algorithm and a regret bound governed by the geometric sharpness of the safe set.","feed_headline":"No agent can gain privacy without breaking the regret budget","feed_subtitle":"Privacy slots scale with how tightly each agent's responses bind to the shared safety constraint.","key_machinery":"The machinery has three parts. First, the sharpness of the safe set, $\\mathrm{Sharp}^{\\infty}_{S'}(\\Delta)$, defined as the maximal Euclidean distance from a point in the safe set to the $\\Delta$-shrunk safe set; for a transformed simplex it evaluates exactly to $\\Delta\\sqrt{(M-1) + (2q'\\tilde{\\rho} - 1)^2}$, with $\\rho_m = c_m/\\beta_{T,m}$ the ratio of the constraint width to that agent's confidence radius. Second, the limiting regret constant $r(a) = \\lim_{T\\to\\infty} r(T,a)/(T^2 \\log T)^{1/3}$, which after substitution takes the form $2LK\\bigl(d(R^2 + \\tilde{\\alpha}^2\\sigma^2)\\bigr)^{1/3}\\left(\\frac{2S\\sqrt{M}}{\\check{\\lambda}} + \\sqrt{(M-1) + (2f(a)-1)^2}\\right)$, where $f(a) = \\max_m \\sum_{m'} \\frac{c_m\\sqrt{R^2 + \\alpha_{m'}^2\\sigma^2}}{c_{m'}\\sqrt{R^2 + \\alpha_m^2\\sigma^2}}$. Third, the ratio-symmetry fact that $f(a) \\ge M$ with equality exactly when the scaled radii $h_m(\\alpha_m) = c_m\\sqrt{R^2 + \\alpha_m^2\\sigma^2}$ are all equal; this identity is what certifies that perturbing $a^*$ in any single coordinate strictly increases $r(a)$.","core_discovery":"The paper claims that the privacy vector $a^*$ with components $\\alpha^*_m = \\sqrt{\\left(R^2/\\sigma^2 + \\tilde{r}^2\\right)\\frac{c_m^2}{\\tilde{c}^2} - \\frac{R^2}{\\sigma^2}}$, where $\\tilde{c} = \\max_m c_m$ and $\\tilde{r}$ is chosen so that the limiting regret constant equals the budget $U$, belongs to the set $A^*$ of unilaterally unimprovable privacy levels (Theorem 3). Concretely, this means $r(a^* + v) > U$ for every nonzero $v \\in \\mathbb{R}_+^M$: any strictly stronger privacy for one agent, with all other agents' privacy levels unchanged, pushes the limiting regret bound past the allowed budget. In the noiseless case $R = 0$ the formula reduces to $\\alpha^*_m = \\tilde{r}\\, c_m/\\tilde{c}$, so each agent's privacy level is proportional to the tightness $c_m$ of the safety constraint in that agent's direction, and agents whose responses are more tightly constrained receive weaker privacy. The proof relies on an exact expression for the sharpness of a transformed simplex, which is minimized when the scaled constraint widths $\\rho_m = c_m/\\beta_{T,m}$ are equal across agents.","pith_inferences":["The paper's privacy guarantee (Fact 1) is proved per time step and never composed over the $T$ rounds; if the full adaptively-chosen transcript is the real privacy object, the effective $(\\varepsilon,\\delta)$ is weaker and the confidence radii $\\beta_{t,m}$, hence the whole tradeoff curve, would have to be recomputed. The unimprovability result is stated for the per-step guarantee as given.","The proportionality rule of Corollary 1 suggests a transferable design heuristic: allocate privacy-loss budget inversely to an agent's marginal contribution to feasibility, a principle that could apply to other safety-critical data-sharing settings beyond bandits.","The proof's ratio-symmetry structure ($f(a) \\ge M$ with equality at equal scaled radii) hints at a broader principle: any safety-and-privacy objective whose regret constant depends on such a ratio will have its unimprovable point at the symmetric allocation, so analogous vectors should exist for other noise mechanisms and other constraint geometries.","A testable extension would rerun the same unimprovability program with Laplace or truncated noise per agent; the sharpness machinery survives, but the Gaussian structure that makes $h_m(\\alpha_m)$ depend on $\\alpha_m^2$ must be replaced."],"forward_implications":["For a fixed regret budget $U$, the vector $a^*$ satisfies $r(a^*) = U$ exactly, and any unilateral increase in one agent's privacy level makes $r(a) > U$, so each agent's privacy is individually maxed out within the budget.","In the noiseless setting $R = 0$, privacy levels are allocated in proportion to the constraint-tightness parameters $c_m$: agents whose responses sit under tighter safety constraints get weaker privacy (Corollary 1).","For simplex safe sets the regret of the algorithm grows as $O(T^{2/3}(\\log T)^{1/3})$, with the leading constant set by the privacy noise variance and by the sharpness of the scaled safe set.","The sharpness of the transformed simplex is smallest when all scaled constraint widths $\\rho_m$ are equal (Lemma 11), making a symmetric simplex the most favorable geometry for regret.","For any polytopic safe set, Theorem 2 splits regret into a safety term (sharpness times the shrinkage of the safe set) and an optimism term, with privacy entering only through the confidence radii $\\beta_{T,m}$."],"supporting_citations":[{"why":"Supplies the Safe-LUCB algorithm that Safe-Private Lin-UCB generalizes, plus the pure-exploration lemma lower-bounding the minimum eigenvalue of the Gram matrix.","marker":"[4]"},{"why":"Introduces the sharpness of a safety-constraint set, the geometric quantity the regret bound is expressed through.","marker":"[5]"},{"why":"Provides the confidence-ellipsoid theorem and the elliptic potential lemma that define the confidence radii and bound the optimism regret term.","marker":"[22]"},{"why":"Gives the Gaussian mechanism and the differential privacy definitions underlying each agent's local perturbation.","marker":"[8]"},{"why":"Supplies the normal-cone optimality characterization used to prove the exact sharpness formula of the transformed simplex.","marker":"[23]"},{"why":"Provides the refined Gaussian-mechanism variance constant used to set the noise scale in the numerical experiments.","marker":"[24]"}],"fun_headline_variants":["More privacy for one agent breaks the regret budget","Privacy gains cost regret in safety-constrained bandits","Optimal privacy: any extra protection busts the regret cap","Sharp tradeoff: privacy, safety, and regret in linear bandits"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The paper proves the local differential privacy guarantee only for a single round of responses at a time, and never shows that the full $T$-round interaction, in which the coordinator's actions depend on all past private responses, satisfies the same $(\\varepsilon_m,\\delta)$-LDP; the confidence radii that drive the regret bound would change if full-sequence privacy were the intended guarantee.","fun_headline_variants_meta":{"raw":{"variants":["More privacy for one agent breaks the regret budget","Privacy gains cost regret in safety-constrained bandits","Optimal privacy: any extra protection busts the regret cap","Sharp tradeoff: privacy, safety, and regret in linear bandits"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000241,"raw_usage":{"total_tokens":1540,"prompt_tokens":982,"completion_tokens":558,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":598,"completion_tokens_details":{"reasoning_tokens":490}},"tokens_in":598,"tokens_out":558,"duration_ms":5505,"temperature":1.0,"reasoning_tokens":490,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T11:05:36.395251+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Evaluate Lemma 13's formula at $a^* + v$ for a concrete simplex and a single positive coordinate of $v$: the unimprovability claim reduces to the arithmetic fact that $f(a) > M$ whenever the scaled radii $h_m(\\alpha_m)$ are not all equal, so a single evaluation that gave $r(a^* + v) \\le U$ would refute it. Separately, compose the per-round Gaussian mechanism over $T$ rounds under the algorithm's adaptive action rule (for instance by standard advanced composition) and compare the composed privacy parameter with the $\\varepsilon_m$ used in the confidence radii; a gap would show that the regret budget $U$ was calibrated with the wrong privacy parameter.","supporting_citations":[{"cited_title":"The impact of the geo- metric properties of the constraint set in safe optimization with bandit feedback,","cited_arxiv_id":null,"evidence_quote":"Introduces the sharpness of a safety-constraint set, the geometric quantity the regret bound is expressed through."},{"cited_title":"Improved algorithms for linear stochastic bandits,","cited_arxiv_id":null,"evidence_quote":"Provides the confidence-ellipsoid theorem and the elliptic potential lemma that define the confidence radii and bound the optimism regret term."}],"review_version":1}