{"id":"b4a3e4db-cbf8-42bf-8ef0-abe6459012e6","arxiv_id":"2505.02383","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"low","formal_verification":"none","parameter_count":1,"one_line_summary":"A new bandit algorithm, DP-TS-UCB, achieves a tunable privacy-regret trade-off, improving the privacy guarantee of Gaussian Thompson Sampling from O(sqrt(T)) to O(T^0.25) while preserving near-optimal regret.","lead":"This paper designs a new algorithm for online decision-making under privacy constraints that tunes the balance between how private the decisions are and how much reward is lost. It shows that the algorithm can get much stronger privacy than prior Thompson Sampling methods while keeping near-optimal regret.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Privacy proof omits adaptive composition across epochs; claimed T^{0.25(1-alpha)}-GDP may require an additional sqrt(log T) factor or more.","rationale":"DP-TS-UCB's headline contribution is the privacy-regret trade-off, and the load-bearing step is Theorem 4.4. The proof's one-epoch argument would be sufficient only if a changed observation could influence at most phi released values. In sequential decision making, however, the released actions determine the future observations that are fed into later empirical means; a single changed reward can therefore alter the entire future transcript even after the reward itself is abandoned. The reader's weakest assumption (each observation used exactly once) is necessary but not sufficient; one must also control the adaptive feedback across epochs. The doubling epoch structure is the natural tool: if per-round GDP for an epoch with n observations scales as 1/sqrt(n ln^alpha), then the squared GDP contributions across epochs sum geometrically and the claimed T^{0.25(1-alpha)}-GDP bound survives with at most a constant factor. The paper does not provide this argument, and its invocation of Lemma 5 of Ou et al. (2024) is ambiguous about the n-dependence. A secondary issue is that the worst-case regret stated in Theorem 4.2 as ln^{0.5(1+alpha)} does not match the proof's own conclusion ln^{1+alpha}; this is a likely typo and does not affect the privacy trade-off, but it should be corrected. Because the missing composition argument is central but plausibly fixable, the appropriate verdict remains CONDITIONAL: the paper should be accepted only after Theorem 4.4 is proven by explicit epoch-wise composition that accounts for the adaptive data selection across epochs.","tokens_in":26887,"tokens_out":52321,"duration_ms":690241,"concrete_test":"Independently re-derive the GDP guarantee for Algorithm 1 by explicit adaptive composition over epochs. For each epoch r with n_r observations, derive the GDP of the phi actions in that epoch as eta_r = c / sqrt(n_r ln^alpha(T)), either from Lemma 5 of Ou et al. (2024) or from a direct Gaussian anti-concentration argument, making the dependence on n_r explicit. Then compute the total squared GDP as the sum over epochs of phi * eta_r^2, using n_{r+1} = 2 n_r. If the sum is phi * ln^alpha(T)^{-1} times a constant, Theorem 4.4 is validated; if it is phi * ln^alpha(T)^{-1} * log T, the claimed T^{0.25(1-alpha)}-GDP bound is invalid and the privacy-regret trade-off degrades. The same check should verify whether Lemma 5's per-round GDP parameter is constant or proportional to 1/sqrt(n).","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The proof of Theorem 4.4 fixes one changed reward and argues that it enters one Gaussian distribution and that at most phi samples are drawn from it, so the GDP loss is sqrt(phi/ln^alpha(T)). This is not sufficient in an adaptive bandit: those phi samples change the actions during the epoch, which changes which rewards are observed, and those observed rewards determine the empirical means for every later epoch. The changed reward therefore propagates through data selection to all future epochs, even after the reward itself is abandoned. Direct reuse is bounded by the epoch structure, but indirect influence through action-dependent data collection is not addressed.\n\nTo obtain a sub-sqrt(T) guarantee one must show that the per-round action privacy decays as 1/sqrt(n ln^alpha(T)) and that the epoch sizes double, so the squared GDP contributions over epochs form a geometric series (1 + 1/2 + 1/4 + ...). The paper never states or proves this n-dependence; it only invokes Lemma 5 of Ou et al. (2024) as a per-round privacy bound and then composes the mandatory and optional phases of one epoch. If Lemma 5 is read as a constant per-round bound, adaptive composition over the rounds of all future epochs would give O(sqrt(T))-GDP, eliminating the claimed improvement. The epoch structure may rescue the result, but the proof as written does not establish the needed composition.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes DP-TS-UCB, a private stochastic bandit algorithm that combines Thompson Sampling with Gaussian priors and UCB-style exploration. The algorithm introduces a sampling budget φ per arm-specific epoch so that at most φ Gaussian mean-reward samples are drawn from each data-dependent Gaussian distribution; after the budget is exhausted, the algorithm reuses the maximum of the already-sampled models. For a trade-off parameter α∈[0,1], the authors claim a Gaussian differential privacy (GDP) guarantee of order O~(T^{0.25(1−α)}) and a problem-dependent regret bound of order O(K ln^{α+1}(T)/Δ), with a worst-case regret of O(sqrt(KT ln^{0.5(1+α)}(T))). The regret analysis is developed in detail in the appendix using concentration and anti-concentration bounds for Gaussians. The privacy analysis in Section 4.3 argues that a changed reward enters only one empirical mean, from which at most φ samples are drawn, and then composes the mandatory TS-Gaussian and optional UCB phases of that single epoch.","tokens_in":27089,"tokens_out":18898,"duration_ms":185391,"significance":"If the privacy claim is correct, the paper offers a substantial improvement over the O(sqrt(T))-GDP guarantee of TS-Gaussian (Ou et al., 2024) while maintaining near-optimal regret, and it provides a tunable privacy–regret trade-off. The conceptual connection between Thompson Sampling and UCB through the maximum of φ Gaussian samples (Lemma 4.1) is interesting and may be of independent value. The regret analysis is rigorous and substantial, with the key lemmas (C.1, D.1–D.3) proven in the appendix. However, the privacy analysis has a load-bearing gap: it does not address the adaptive composition of privacy losses across epochs when the changed reward influences future action-dependent data collection. Because the sub-sqrt(T) GDP guarantee is the central novelty, this gap is serious.","major_comments":[{"comment":"The proof argues that a single changed reward affects only one empirical mean and hence at most φ Gaussian samples in one epoch, and then composes the mandatory and optional phases of that epoch. This reasoning is incomplete because the φ samples determine the actions taken during the epoch, and those actions determine which rewards are observed in all subsequent rounds. The changed reward therefore propagates through the action-dependent data collection to all future epochs, even after the reward is no longer used directly. The statement 'X_j(τ) will not be used to construct Gaussian distributions starting from epoch r_j+1' is true only for direct reuse; the distributions in later epochs are built from observations whose selection was influenced by X_j(τ). To establish the claimed sub-sqrt(T) GDP guarantee, the authors must show that the per-round privacy loss decays with the epoch size and that the doubling epoch sizes yield a geometric composition, or otherwise bound the adaptive composition over all epochs. As written, the proof does not rule out an O(sqrt(T))-GDP guarantee, which would negate the main claimed improvement.","section":"Section 4.3, proof of Theorem 4.4"},{"comment":"The proof invokes 'Lemma 5 of Ou et al. (2024)' for the per-round GDP guarantee without stating the lemma or explaining how the scaled variance ln^α(T)/n_i modifies its applicability. A reader cannot verify that the per-round GDP parameter is indeed sqrt(1/ln^α(T)) independent of n_i, nor can one check whether the lemma covers the adaptive bandit setting. The paper should state the lemma (or provide a self-contained proof) and clarify the dependence on the number of observations n_i used in the empirical mean.","section":"Section 4.3, proof of Theorem 4.4"}],"minor_comments":[{"comment":"The paper notes in the conclusion that DP-TS-UCB is not anytime and requires the horizon T as input (to set φ). This limitation should be stated in the introduction as well, since it affects practical applicability.","section":"Section 1 and Section 6"},{"comment":"The regret expression contains a misplaced closing parenthesis: 'O(K ln(TΔ^2) ln(T)/Δ) + K ln ln(T) ln(T)/Δ)' should have the final parenthesis removed.","section":"Table 1, DP-TS-UCB (α=1) row"},{"comment":"Fact A.1 is stated for T > e^3, but this qualification is omitted in the main text where the proof sketch references the lemma. The authors should remind readers of this condition when applying the lemma in the regret bound.","section":"Appendix B, proof of Lemma 4.1"},{"comment":"The privacy proof would benefit from an explicit statement of how the GDP parameter is computed from the composition of the two phases, including the precise use of Theorem 4.7 and Theorem 4.8; currently the jump from the per-phase bounds to the final GDP parameter is abbreviated.","section":"Section 4.3, Theorem 4.4"}],"recommendation":"major_revision","confidential_remarks":"The likely main issue is the privacy analysis: the claimed O~(T^{0.25(1−α)})-GDP guarantee rests on bounding the influence of a changed reward within a single epoch, but the mechanism is adaptive and the changed reward can alter the entire future trajectory through action-dependent data collection. This is a load-bearing gap, not merely a presentation issue. If the authors cannot supply a rigorous adaptive-composition argument, the main contribution is in question. I would ask for a substantial revision of Section 4.3 and a careful treatment of the interaction between the epoch structure and the GDP composition theorem."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The core idea is genuinely new: cap the number of Gaussian posterior draws per epoch and reuse the maximum as a UCB-style bonus. That gives a tunable privacy-regret trade-off that I have not seen before, and the regret analysis is detailed and largely checks out. The lemmas in the appendix (C.1, D.1-D.3) are real work, and the comparison to M-TS-Gaussian is honest. The soft spot is Theorem 4.4. The proof argues that a changed observation affects exactly one Gaussian distribution and that at most phi samples are drawn from it, so the GDP loss is sqrt(phi/ln^alpha). That is fine for direct reuse, but it never bounds the indirect influence: those phi samples change the actions during the epoch, which changes which rewards are observed in every later epoch. Even after the observation is discarded, its effect propagates through the data-dependent collection of future observations. The proof as written does not address this, so the claimed O~(T^{0.25(1-alpha)})-GDP is not supported by the argument given. The stress-test is right that if Lemma 5 of Ou et al. is read as a constant per-round bound, then adaptive composition over all rounds gives O(sqrt(T))-GDP, and the claimed improvement disappears. The epoch structure may rescue the result, but the paper needs a geometric-decay argument (per-round privacy decaying as 1/sqrt(n ln^alpha)) or a stability-based coupling argument. That is a load-bearing gap, not a cosmetic one. Minor issues: the paper calls the alpha=0 regret bound optimal despite the 1.5 ln T constant; the experiments lack error bars and code; and the privacy proof invokes Lemma 5 without showing how the scaled variance ln^alpha(T)/n changes the per-round GDP. These are addressable. The right reader is someone working on differentially private bandits or on the composition of adaptive algorithms. The algorithm idea is worth knowing, and the regret analysis is worth reading, but the main privacy claim should not be taken at face value. This deserves a serious referee, and I would engage with it, but I would not cite it for the GDP result until the composition gap is closed.","headline":"Clever algorithm and solid regret analysis, but the privacy proof misses the adaptive-composition problem and the main GDP claim is not established as written.","tokens_in":671,"tokens_out":806,"would_cite":false,"duration_ms":149289,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"DP-TS-UCB trades privacy and regret with a single parameter, reaching $\\tilde{O}(T^{0.25})$-GDP without losing near-optimal regret.","keywords":["differential privacy","stochastic bandits","Thompson Sampling","Gaussian differential privacy","Upper Confidence Bound","regret bounds","privacy-regret trade-off","Gaussian anti-concentration"],"falsifier":"A concrete test is to instrument DP-TS-UCB and verify the single-use assumption: for every pulled arm, record the epoch counter, observation counter, and remaining sampling budget, and confirm that no reward contributes to more than one empirical mean and no Gaussian distribution ever produces more than $\\phi$ samples. A direct statistical check is to simulate two neighboring reward streams and estimate the trade-off function of the algorithm's output; if the measured $\\delta(\\varepsilon)$ is not bounded by $\\Phi(-\\varepsilon/\\eta+\\eta/2)-e^{\\varepsilon}\\Phi(-\\varepsilon/\\eta-\\eta/2)$ with $\\eta=\\sqrt{2c_0T^{0.5(1-\\alpha)}\\ln^{1.5(1-\\alpha)}(T)}$ as $T$ grows, the claim fails.","tokens_in":26630,"feed_emoji":"🎰","tokens_out":12212,"duration_ms":112041,"temperature":0.7,"pith_summary":"This paper proposes DP-TS-UCB, a stochastic bandit algorithm that draws at most a budgeted number of Gaussian samples from each arm's empirical-mean distribution and then reuses the largest sampled value, so exploration switches from Thompson-Sampling-style randomness to UCB-style optimism. The central claim is a tunable privacy-regret trade-off: with a parameter $\\alpha\\in[0,1]$, the algorithm satisfies a Gaussian differential privacy (GDP) guarantee of order $\\tilde{O}(T^{0.25(1-\\alpha)})$ and achieves problem-dependent regret $\\sum_{i:\\Delta_i>0} O(\\ln(T^{0.5(3-\\alpha)}\\Delta_i^2)\\ln^{\\alpha}(T)/\\Delta_i + (3-\\alpha)\\ln\\ln(T)\\ln^{\\alpha}(T)/\\Delta_i)$, with worst-case regret $O(\\sqrt{KT\\ln^{0.5(1+\\alpha)}(T)})$. Setting $\\alpha=0$ yields $O(K\\ln(T)/\\Delta)$-type problem-dependent regret while improving the privacy guarantee from $O(\\sqrt{T})$-GDP to $\\tilde{O}(T^{0.25})$-GDP, and setting $\\alpha=1$ yields a constant GDP guarantee at the price of an extra $\\ln(T)$ factor in regret. The argument turns Gaussian anti-concentration into a UCB-style optimism lemma, and uses an arm-specific epoch structure so that each observation enters at most one empirical-mean estimate. If the paper is right, private sequential decision-making can enjoy a smooth frontier between strong privacy and near-optimal regret.","feed_headline":"Capped Thompson sampling gets $T^{1/4}$ privacy at no regret cost","feed_subtitle":"The same algorithm tunes the privacy parameter from $\\tilde{O}(T^{1/4})$-GDP down to $O(1)$-GDP.","key_machinery":"The load-bearing identity is Lemma 4.1, a Gaussian anti-concentration inequality: for $\\theta^{(1)}_{i,s},\\ldots,\\theta^{(\\phi)}_{i,s}$ i.i.d. according to $\\mathcal{N}(\\hat{\\mu}_{i,s},\\ln^{\\alpha}(T)/s)$, the maximum exceeds the true mean with probability at least $1-O(1/T)$. This is what turns the largest of the $\\phi$ budgeted samples into a UCB-style confidence bound once fresh sampling is no longer allowed. The other load-bearing piece is the arm-specific epoch structure, which increments the epoch index only when the number of unprocessed observations reaches $2^{r_i}$, so each reward enters exactly one empirical mean; this is what limits the privacy composition to $\\phi$ Gaussian draws per affected distribution. Together they make the algorithm a hybrid: a mandatory Thompson-Sampling phase with fresh Gaussian samples and an optional UCB phase that reuses the best sampled model.","core_discovery":"The paper establishes that for any trade-off parameter $\\alpha\\in[0,1]$, DP-TS-UCB satisfies a Gaussian differential privacy guarantee of order $\\tilde{O}(T^{0.25(1-\\alpha)})$, while achieving problem-dependent regret $$\\sum_{i:\\Delta_i>0} O\\left(\\frac{\\ln($T^{{0.5(3-\\alpha)}}$\\$Delta_i^{2}$)\\$ln^{{\\alpha}}$(T)}{\\Delta_i} + \\frac{(3-\\$\\alpha$)\\ln\\ln(T)\\$ln^{{\\alpha}}$(T)}{\\Delta_i}\\right)$$ and worst-case regret $O(\\sqrt{KT\\ln^{0.5(1+\\alpha)}(T)})$. This is the paper's central discovery: privacy and regret can be traded continuously by a single parameter, and at $\\alpha=0$ the privacy guarantee improves from the previous $O(\\sqrt{T})$-GDP to $\\tilde{O}(T^{0.25})$-GDP while retaining near-optimal problem-dependent regret. The mechanism is a two-phase exploration: after an arm's empirical mean is updated, the algorithm spends a budget of $\\phi$ fresh Gaussian mean-reward samples; once the budget is exhausted, it stops sampling and reuses the largest of those samples as a deterministic optimism term, exactly the role played by a UCB bonus. The privacy analysis uses the fact that each reward is folded into at most one empirical mean, so a single changed reward influences only one Gaussian distribution, from which at most $\\phi$ samples are drawn.","pith_inferences":["A natural extension the paper leaves implicit is to make the sampling budget depend on the observed gaps, turning the horizon-dependent GDP guarantee into a problem-dependent one.","The same two-phase scheme could be transplanted to other Thompson Sampling variants or contextual bandits whenever the posterior family has a usable anti-concentration bound; this is an editorial extrapolation, not something the paper demonstrates.","A testable consequence of the regret analysis is that the optional UCB phase contributes only $O(\\ln(T))$ regret, so increasing $\\phi$ should not visibly raise regret while it does weaken privacy."],"forward_implications":["At $\\alpha=0$, DP-TS-UCB attains $O(K\\ln(T)/\\Delta)$ problem-dependent regret with an $\\tilde{O}(T^{0.25})$-GDP guarantee, improving privacy over unmodified Thompson Sampling with Gaussian priors without changing the regret order.","At $\\alpha=1$, the GDP parameter is constant in $T$, so increasing the horizon no longer increases privacy loss, at the cost of an extra $\\ln(T)$ factor in problem-dependent regret.","Intermediate values of $\\alpha$ interpolate between these extremes, with worst-case regret $O(\\sqrt{KT\\ln^{0.5(1+\\alpha)}(T)})$.","DP-TS-UCB is not an anytime algorithm: the sampling budget depends on knowing $T$ and $\\alpha$ in advance, so its guarantees are tied to a fixed horizon."],"supporting_citations":[{"why":"Supplies the near-optimal Thompson Sampling regret analysis whose lemmas are refined in Lemma C.1 and used in bounding the TS-phase regret term.","marker":"Agrawal & Goyal (2017)"},{"why":"Defines UCB1 and the optimism principle that the reuse of MAX_i is meant to emulate.","marker":"Auer et al. (2002)"},{"why":"Establishes the $O(\\sqrt{T})$-GDP baseline for Thompson Sampling with Gaussian priors and provides the per-round Gaussian mechanism lemma used in the composition argument.","marker":"Ou et al. (2024)"},{"why":"Defines Gaussian differential privacy and supplies the composition and post-processing theorems used to convert per-round privacy losses into the GDP guarantee.","marker":"Dong et al. (2022)"},{"why":"Provides the differential privacy definitions and Gaussian mechanism background that frame the problem and the privacy accounting.","marker":"Dwork et al. (2014)"},{"why":"Introduces the arm-specific epoch structure used to ensure each observation is used only once in an empirical mean.","marker":"Hu et al. (2021)"},{"why":"Supplies prior private bandit analysis with the same epoch-structure idea and lower bounds the regret guarantees are compatible with.","marker":"Azize & Basu (2022)"}],"fun_headline_variants":["One knob tunes privacy from T^{1/4} down to constant","Trading privacy and regret with a single parameter","TS meets UCB: privacy improves to T^{1/4} at no regret cost","A single alpha tunes privacy-regret trade-off continuously","Better privacy, same regret: Thompson sampling with UCB twist"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The privacy guarantee collapses if the arm-specific epoch structure does not genuinely ensure that each observed reward is used in exactly one empirical-mean update and then discarded; if a single changed reward could influence more than one Gaussian distribution, or more than $\\phi$ samples were drawn from an affected distribution, the GDP composition bound would be larger than claimed.","fun_headline_variants_meta":{"raw":{"variants":["One knob tunes privacy from T^{1/4} down to constant","Trading privacy and regret with a single parameter","TS meets UCB: privacy improves to T^{1/4} at no regret cost","A single alpha tunes privacy-regret trade-off continuously","Better privacy, same regret: Thompson sampling with UCB twist"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00062,"raw_usage":{"total_tokens":2912,"prompt_tokens":1018,"completion_tokens":1894,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":634,"completion_tokens_details":{"reasoning_tokens":1805}},"tokens_in":634,"tokens_out":1894,"duration_ms":15420,"temperature":1.0,"reasoning_tokens":1805,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T00:54:48.533516+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"A concrete test is to instrument DP-TS-UCB and verify the single-use assumption: for every pulled arm, record the epoch counter, observation counter, and remaining sampling budget, and confirm that no reward contributes to more than one empirical mean and no Gaussian distribution ever produces more than $\\phi$ samples. A direct statistical check is to simulate two neighboring reward streams and estimate the trade-off function of the algorithm's output; if the measured $\\delta(\\varepsilon)$ is not bounded by $\\Phi(-\\varepsilon/\\eta+\\eta/2)-e^{\\varepsilon}\\Phi(-\\varepsilon/\\eta-\\eta/2)$ with $\\eta=\\sqrt{2c_0T^{0.5(1-\\alpha)}\\ln^{1.5(1-\\alpha)}(T)}$ as $T$ grows, the claim fails.","supporting_citations":[{"cited_title":"and Goyal, N","cited_arxiv_id":null,"evidence_quote":"Supplies the near-optimal Thompson Sampling regret analysis whose lemmas are refined in Lemma C.1 and used in bounding the TS-phase regret term."},{"cited_title":"Finite-time analysis of the multi-armed bandit problem","cited_arxiv_id":null,"evidence_quote":"Defines UCB1 and the optimism principle that the reuse of MAX_i is meant to emulate."},{"cited_title":"and Basu, D","cited_arxiv_id":null,"evidence_quote":"Supplies prior private bandit analysis with the same epoch-structure idea and lower bounds the regret guarantees are compatible with."}],"review_version":1}