Pith. sign in

REVIEW 1 major objections 5 minor 46 references

Optimal Regret of Bernoulli Bandits under Global Differential Privacy

T0 review · 1 major / 5 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read For Bernoulli bandits under global differential privacy, the optimal asymptotic regret is governed by one divergence $d_\epsilon$ that interpolates KL and total variation.

desk verdict 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. read the letter →

arxiv 2505.05613 v1 pith:U775F34F submitted 2025-05-08 stat.ML cs.CRcs.ITcs.LGmath.ITmath.STstat.TH

Achraf Azize , Yulian Wu , Junya Honda , Francesco Orabona , Shinji Ito , Debabrota Basu This is my paper · ORCID
classification stat.MLcs.CRcs.ITcs.LGmath.ITmath.STstat.TH MSC 62L0568T05
keywords BernoullibanditsglobaldifferentialprivacyregretlowerboundLaplacemechanismKLdivergencetotalvariationdistanceconcentrationinequalitymulti-armed
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

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

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

1 major / 5 minor

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.

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 (1)
  1. [Appendix F, proof of Theorem 25 (Eq. (45))] 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.
minor comments (5)
  1. [Section 4, comments after Theorem 9] The word 'georemetrically' should be 'geometrically'; similar typos appear in the appendices (e.g., 'tet', stray arrows in displayed equations).
  2. [Appendix D, proof of Lemma 19] 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.
  3. [Appendix D, proof of Corollary 20] 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.
  4. [Section 3, proof of Theorem 5] 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.
  5. [Appendix B, Figure 2 caption] The second panel is said to be run with b=L, which appears to be a typo for b=R.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: d_epsilon is derived from independent privacy and concentration arguments, and the matching regret bounds are genuine derivations.

full rationale

I walked the claimed derivation chain and found no step where a prediction or first-principles result reduces to its own inputs by construction. The lower bound (Theorem 5) is proved from group privacy plus a double change of environment (Lemma 15): d_epsilon emerges as the optimized sum of an epsilon-TV transport cost and a KL transport cost, not as a quantity chosen to match the algorithms' regret. The upper bound (Theorem 9) rests on the standalone concentration statement Proposition 7 / Lemma 19, which computes the tail of a convolution of Bernoulli and Laplace sums and independently produces d_epsilon in the exponent; the matching of upper and lower bounds is then a derived consequence, not an assumed one. The algorithms use d_epsilon in their indexes, but designing an algorithm around a proven lower-bound complexity measure is standard and is not circular as long as the regret analysis is nontrivial, which it is here (batched pulls, convergence phases, and the batch-ratio alpha factor). Self-citations to Azize and Basu (2022, 2024) are contextual: the paper improves the prior lower bound rather than importing it, and the Table/View DP equivalence is reproved in Appendix B rather than merely cited as an unverified premise. The reviewer-flagged issue in Eq. (45), where Corollary 20 is applied with d_epsilon(mu_i+delta'/epsilon, mu_star) instead of d_epsilon(mu_i+delta'/epsilon, mu_i), is a potential correctness gap in the proof as written, not circularity: it does not make the theorem's claim identical to its assumptions, and the concentration lemma itself remains an externally checkable probabilistic statement. Overall, the paper is self-contained against standard bandit and DP tools, and I found no load-bearing circular reduction.

Assumptions & free parameters 2 free parameters · 4 assumptions · 0 invented entities

No new physical or conceptual entities are introduced. The quantity d_epsilon is a derived mathematical expression, not an entity. The free parameters are limited to the batch ratio and initial batch size, both design choices that do not affect the asymptotic rate. The axioms are standard probabilistic, information-theoretic, and DP background facts plus the Bernoulli and batching assumptions.

free parameters (2)
  • alpha (batch ratio) = >1, arbitrary close to 1 (e.g., 2 in experiments, 1.1 in Figure 8)
    Ratio of the geometrically increasing batch sizes in Algorithm 1, Eq. (14). It controls the phase schedule and appears as the multiplicative constant in the regret upper bound of Theorem 9. It is a design parameter, not fitted to data, but it is central to the matching claim as alpha approaches 1.
  • n0 (initial batch size) = 1 in experiments (Section 5)
    Initial number of pulls for each arm in Algorithm 1, Line 1. It affects only additive lower-order terms in the regret and is chosen by hand.
assumptions (4)
  • standard math Chernoff bound via KL divergence and asymptotic maximal Hoeffding inequality (Lemmas 32 and 33)
    Used in the lower bound proof to control the events A^c and L^c, and in the upper bound proof for the concentration of private means.
  • standard math Standard DP properties: post-processing, group privacy, composition, parallel composition, Laplace mechanism (Propositions 27-29, Lemma 30, Theorem 31)
    Foundational for the privacy analysis in Proposition 8 and for the double change of environment in the lower bound proof.
  • domain assumption Rewards are Bernoulli with means in [0,1] and optimal mean mu_star < 1
    The concentration inequality and regret upper bound are stated for Bernoulli rewards, and the assumption mu_star < 1 excludes the degenerate case where d_epsilon(mu,1) is infinite for mu<1.
  • domain assumption Geometric batch sizes with ratio alpha > 1 and m/n_m = o(1) for each arm
    The no-forgetting design requires the number of accumulated Laplace noises per arm to be negligible relative to the number of pulls; the geometric schedule gives m = O(log T) phases, which satisfies this requirement.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Optimal Regret of Bernoulli Bandits under Global Differential Privacy." pith.science (2026). https://pith.science/paper/U775F34F

@misc{pith2026250505613,
  author       = {Pith},
  title        = {Pith review of: Optimal Regret of Bernoulli Bandits under Global Differential Privacy},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/U775F34F}},
  note         = {Machine review of arXiv:2505.05613}
}
abstract

As sequential learning algorithms are increasingly applied to real life, ensuring data privacy while maintaining their utilities emerges as a timely question. In this context, regret minimisation in stochastic bandits under $\epsilon$-global Differential Privacy (DP) has been widely studied. Unlike bandits without DP, there is a significant gap between the best-known regret lower and upper bound in this setting, though they "match" in order. Thus, we revisit the regret lower and upper bounds of $\epsilon$-global DP algorithms for Bernoulli bandits and improve both. First, we prove a tighter regret lower bound involving a novel information-theoretic quantity characterising the hardness of $\epsilon$-global DP in stochastic bandits. Our lower bound strictly improves on the existing ones across all $\epsilon$ values. Then, we choose two asymptotically optimal bandit algorithms, i.e. DP-KLUCB and DP-IMED, and propose their DP versions using a unified blueprint, i.e., (a) running in arm-dependent phases, and (b) adding Laplace noise to achieve privacy. For Bernoulli bandits, we analyse the regrets of these algorithms and show that their regrets asymptotically match our lower bound up to a constant arbitrary close to 1. This refutes the conjecture that forgetting past rewards is necessary to design optimal bandit algorithms under global DP. At the core of our algorithms lies a new concentration inequality for sums of Bernoulli variables under Laplace mechanism, which is a new DP version of the Chernoff bound. This result is universally useful as the DP literature commonly treats the concentrations of Laplace noise and random variables separately, while we couple them to yield a tighter bound.

Figures

Figures reproduced from arXiv: 2505.05613 by the authors.

Figure 1
Figure 1. Evolution of the regret over time for DP-SE, AdaP-KLUCB, Lazy-DP-TS, DP-KLUCB, and DP-IMED for ϵ = 0.25, and Bernoulli bandits µ1 (left) and µ2 (right). Comments. (a) The regret upper bounds of DP-IMED and DP-KLUCB match asymptotically the lower bound of Theorem 5 up to the constant α > 1, where α is the ratio of the georemetrically increasing batch sizes Bm. This parameter α > 1 can be set arbitrarily close to 1 to… view at source ↗
Figure 2
Figure 2. Interactive protocol in the adaptive continual release model between a policy [PITH_FULL_IMAGE:figures/full_fig_p019_2.png] view at source ↗
Figure 3
Figure 3. Different reward representations for T = 3 and K = 2. The highlighted rewards are the rewards observed by the policy for the trajectory (a1, a2, a3) = (1, 2, 1) • Pr[ViewL,t⋆ A(x,x’),π ∈ S] = Mπ x (S). • Pr[ViewR,t⋆ A(x,x’),π ∈ S] = Mπ x’(S). In other words, the batch mechanism Mπ combined with neighbouring tables can be “simu￾lated” using a specific type of “reward-feeding” adversaries that only care about the last… view at source ↗
Figures from the paper (5 more)
Figure 4
Figure 4. Figure 4: Evolution of regret over time for µ1 for different budgets ϵ. Composition is a fundamental property of DP. Composition helps to analyse the privacy of sophisticated algorithms, by understanding the privacy of each building block, and summing di￾rectly the privacy budge…
Figure 5
Figure 5. Figure 5: Evolution of regret over time for µ2 for different budgets ϵ. tk < tk+1 − 1 = n. Let’s define the following mechanism G : {x1, . . . , xn} → O k i=1 Mi {xti ,...,xti+1−1} G is the mechanism that we get by applying each Mi to the i-th partition of the input dataset {x1,…
Figure 6
Figure 6. Figure 6: Evolution of regret over time for µ3 for different budgets ϵ. Theorem 31 (The Laplace Mechanism (Dwork and Roth, 2014)) Let f : X → R k be a deter￾ministic algorithm with ℓ1 sensitivity s1(f) ≜ max D∼D′ ∥f(D) − f(D′ )∥1 . Let ML(f, ϵ) ≜ f + (Y1, . . . , Yk), where Yi a…
Figure 7
Figure 7. Figure 7: Evolution of regret over time for µ4 for different budgets ϵ. • Upper Tail Bound: for any a > µ P(Sn ≥ a) ≤ exp  −n · kl a n , µ n  , where kl(p, q) is defined as kl(p, q) = p log p q + (1 − p) log 1 − p 1 − q . • Lower Tail Bound: for any a < µ P(Sn ≤ a) ≤ exp  −…
Figure 8
Figure 8. Figure 8: Evolution of the regret for T = 107 with respect to ϵ for DP-IMED on µ ≜ [0.8, 0.1, 0.1, 0.1, 0.1], compared to the asymptotic regret lower bound of Theorem 5. 48 [PITH_FULL_IMAGE:figures/full_fig_p048_8.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

46 extracted references · 29 canonical work pages

  1. [1]

    The price of differential privacy for online learning

    Naman Agarwal and Karan Singh. The price of differential privacy for online learning. In International Conference on Machine Learning, pages 32--40. PMLR, 2017

    2017

  2. [2]

    Finite-time analysis of the multiarmed bandit problem

    Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47 0 (2-3): 0 235--256, 2002

    work page 2002

  3. [3]

    When privacy meets partial information: A refined analysis of differentially private bandits

    Achraf Azize and Debabrota Basu. When privacy meets partial information: A refined analysis of differentially private bandits. Advances in Neural Information Processing Systems, 35: 0 32199--32210, 2022

    2022

  4. [4]

    Concentrated differential privacy for bandits

    Achraf Azize and Debabrota Basu. Concentrated differential privacy for bandits. In 2nd IEEE Conference on Secure and Trustworthy Machine Learning, 2024

    work page 2024

  5. [5]

    On the complexity of differentially private best-arm identification with fixed confidence

    Achraf Azize, Marc Jourdan, Aymen Al Marjani, and Debabrota Basu. On the complexity of differentially private best-arm identification with fixed confidence. arXiv preprint arXiv:2309.02202, 2023

    arXiv 2023

  6. [6]

    Differentially private best-arm identification

    Achraf Azize, Marc Jourdan, Aymen Al Marjani, and Debabrota Basu. Differentially private best-arm identification. arXiv preprint arXiv:2406.06408, 2024

    arXiv 2024

  7. [7]

    Differential privacy for multi-armed bandits: What is it and what is its cost? arXiv preprint arXiv:1905.12298, 2019

    Debabrota Basu, Christos Dimitrakakis, and Aristide Tossou. Differential privacy for multi-armed bandits: What is it and what is its cost? arXiv preprint arXiv:1905.12298, 2019

    arXiv 1905

  8. [8]

    Concentration inequalities

    St \'e phane Boucheron, G \'a bor Lugosi, and Olivier Bousquet. Concentration inequalities. In Summer school on machine learning, pages 208--240. Springer, 2003

    2003

Show all 46 references
  1. [9]

    Capp \'e , A

    O. Capp \'e , A. Garivier, O.-A. Maillard, R. Munos, and G. Stoltz. K ullback- L eibler upper confidence bounds for optimal sequential allocation. Annals of Statistics, 41(3): 0 1516--1541, 2013

    2013

  2. [10]

    Hubert Chan, Elaine Shi, and Dawn Song

    T.-H. Hubert Chan, Elaine Shi, and Dawn Song. Private and continual release of statistics. ACM Trans. Inf. Syst. Secur., 14 0 (3), nov 2011. ISSN 1094-9224. doi:10.1145/2043621.2043626. URL https://doi.org/10.1145/2043621.2043626

    2011

  3. [11]

    Combinatorial pure exploration of multi-armed bandits

    Shouyuan Chen, Tian Lin, Irwin King, Michael R Lyu, and Wei Chen. Combinatorial pure exploration of multi-armed bandits. Advances in neural information processing systems, 27, 2014

    2014

  4. [12]

    Zhirui Chen, P. N. Karthik, Yeow Meng Chee, and Vincent Y. F. Tan. Fixed-budget differentially private best arm identification. arXiv preprint arXiv:2401.09073, 2024

    2024 arXiv

  5. [13]

    Shuffle private linear contextual bandits

    Sayak Ray Chowdhury and Xingyu Zhou. Shuffle private linear contextual bandits. arXiv preprint arXiv:2202.05567, 2022

    2022 arXiv

  6. [14]

    The algorithmic foundations of differential privacy

    Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science , 9 0 (3--4): 0 211--407, 2014

    2014

  7. [15]

    Calibrating noise to sensitivity in private data analysis

    Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Proceedings of the Third Conference on Theory of Cryptography, TCC'06, pages 265--284, Berlin, Heidelberg, 2006. Springer-Verlag

    2006

  8. [16]

    Rothblum

    Cynthia Dwork, Moni Naor, Toniann Pitassi, and Guy N. Rothblum. Differential privacy under continual observation. In ACM Symposium on Theory of Computing, STOC '10, page 715–724, New York, NY, USA, 2010. Association for Computing Machinery. ISBN 9781450300506

    2010

  9. [17]

    PAC bounds for multi-armed bandit and M arkov decision processes

    Eyal Even-Dar, Shie Mannor, and Yishay Mansour. PAC bounds for multi-armed bandit and M arkov decision processes. In Conference on Computational Learning Theory, COLT '02, page 255–270, Berlin, Heidelberg, 2002. Springer-Verlag. ISBN 354043836X

    2002

  10. [18]

    Privacy amplification via shuffling for linear contextual bandits

    Evrard Garcelon, Kamalika Chaudhuri, Vianney Perchet, and Matteo Pirotta. Privacy amplification via shuffling for linear contextual bandits. In International Conference on Algorithmic Learning Theory, pages 381--407. PMLR, 2022

    2022

  11. [19]

    Generalized linear bandits with local differential privacy

    Yuxuan Han, Zhipeng Liang, Yang Wang, and Jiheng Zhang. Generalized linear bandits with local differential privacy. Advances in Neural Information Processing Systems, 34: 0 26511--26522, 2021

    2021

  12. [20]

    Differentially private stochastic linear bandits: (almost) for free

    Osama A Hanna, Antonious M Girgis, Christina Fragouli, and Suhas Diggavi. Differentially private stochastic linear bandits: (almost) for free. arXiv preprint arXiv:2207.03445, 2022

    2022 arXiv

  13. [21]

    A note on KL-UCB+ policy for the stochastic bandit

    Junya Honda. A note on KL-UCB+ policy for the stochastic bandit. arXiv preprint arXiv:1903.07839, 2019

    1903 arXiv

  14. [22]

    Non-asymptotic analysis of a new bandit algorithm for semi-bounded rewards

    Junya Honda and Akimichi Takemura. Non-asymptotic analysis of a new bandit algorithm for semi-bounded rewards. J. Mach. Learn. Res., 16: 0 3721--3756, 2015

    2015

  15. [23]

    Near-optimal T hompson sampling-based algorithms for differentially private stochastic bandits

    Bingshan Hu and Nidhi Hegde. Near-optimal T hompson sampling-based algorithms for differentially private stochastic bandits. In Uncertainty in Artificial Intelligence, pages 844--852. PMLR, 2022

    2022

  16. [24]

    Bingshan Hu, Zhiming Huang, and Nishant A. Mehta. Optimal algorithms for private online learning in a stochastic environment, 2021. URL https://arxiv.org/abs/2102.07929

    2021 arXiv

  17. [25]

    The price of differential privacy under continual observation

    Palak Jain, Sofya Raskhodnikova, Satchit Sivakumar, and Adam Smith. The price of differential privacy under continual observation. In International Conference on Machine Learning, pages 14654--14678. PMLR, 2023

    2023

  18. [26]

    The composition theorem for differential privacy

    Peter Kairouz, Sewoong Oh, and Pramod Viswanath. The composition theorem for differential privacy. In International conference on machine learning, pages 1376--1385. PMLR, 2015

    2015

  19. [27]

    Asymptotically efficient adaptive allocation rules

    Tze Leung Lai and Herbert Robbins. Asymptotically efficient adaptive allocation rules. Advances in applied mathematics, 6 0 (1): 0 4--22, 1985

    1985

  20. [28]

    Differentially private linear bandits with partial distributed feedback

    Fengjiao Li, Xingyu Zhou, and Bo Ji. Differentially private linear bandits with partial distributed feedback. In 2022 20th International Symposium on Modeling and Optimization in Mobile, Ad hoc, and Wireless Networks (WiOpt), pages 41--48. IEEE, 2022

    2022

  21. [29]

    Hyperband: A novel bandit-based approach to hyperparameter optimization

    Lisha Li, Kevin Jamieson, Giulia DeSalvo, Afshin Rostamizadeh, and Ameet Talwalkar. Hyperband: A novel bandit-based approach to hyperparameter optimization. The Journal of Machine Learning Research, 18 0 (1): 0 6765--6816, 2017

    2017

  22. [30]

    Bayesian best-arm identification for selecting influenza mitigation strategies

    Pieter JK Libin, Timothy Verstraeten, Diederik M Roijers, Jelena Grujic, Kristof Theys, Philippe Lemey, and Ann Now \'e . Bayesian best-arm identification for selecting influenza mitigation strategies. In Machine Learning and Knowledge Discovery in Databases: European Conferen...

    2018

  23. [31]

    Measurement-based admission control in sliced networks: A best arm identification approach

    Simon Lindst hl, Alexandre Proutiere, and Andreas Johnsson. Measurement-based admission control in sliced networks: A best arm identification approach. In GLOBECOM 2022-2022 IEEE Global Communications Conference, pages 1484--1490. IEEE, 2022

    2022

  24. [32]

    A day at the races: using best arm identification algorithms to reduce the cost of information retrieval user studies

    David E Losada, David Elsweiler, Morgan Harvey, and Christoph Trattner. A day at the races: using best arm identification algorithms to reduce the cost of information retrieval user studies. Applied Intelligence, 52 0 (5): 0 5617--5632, 2022

    2022

  25. [33]

    ( N early) optimal differentially private stochastic multi-arm bandits

    Nikita Mishra and Abhradeep Thakurta. ( N early) optimal differentially private stochastic multi-arm bandits. In Conference on Uncertainty in Artificial Intelligence, 2015

    2015

  26. [34]

    Mitigating bias in adaptive data gathering via differential privacy

    Seth Neel and Aaron Roth. Mitigating bias in adaptive data gathering via differential privacy. In International Conference on Machine Learning, pages 3720--3729. PMLR, 2018

    2018

  27. [35]

    Differentially private kernelized contextual bandits

    Nikola Pavlovic, Sudeep Salgia, and Qing Zhao. Differentially private kernelized contextual bandits. arXiv preprint arXiv:2501.07046, 2025

    2025 arXiv

  28. [36]

    An optimal private stochastic- MAB algorithm based on optimal private stopping rule

    Touqir Sajed and Or Sheffet. An optimal private stochastic- MAB algorithm based on optimal private stopping rule. In International Conference on Machine Learning, pages 5579--5588. PMLR, 2019

    2019

  29. [37]

    Differentially private contextual linear bandits

    Roshan Shariff and Or Sheffet. Differentially private contextual linear bandits. In Advances in Neural Information Processing Systems, pages 4296--4306, 2018

    2018

  30. [38]

    Multi-armed bandits in recommendation systems: A survey of the state-of-the-art and future directions

    N \' collas Silva, Heitor Werneck, Thiago Silva, Adriano CM Pereira, and Leonardo Rocha. Multi-armed bandits in recommendation systems: A survey of the state-of-the-art and future directions. Expert Systems with Applications, 197: 0 116669, 2022

    2022

  31. [39]

    Differentially private multi-armed bandits in the shuffle model

    Jay Tenenbaum, Haim Kaplan, Yishay Mansour, and Uri Stemmer. Differentially private multi-armed bandits in the shuffle model. Advances in Neural Information Processing Systems, 34: 0 24956--24967, 2021

    2021

  32. [40]

    ( N early) optimal algorithms for private online learning in full-information and bandit settings

    Abhradeep Guha Thakurta and Adam Smith. ( N early) optimal algorithms for private online learning in full-information and bandit settings. Advances in Neural Information Processing Systems, 26, 2013

    2013

  33. [41]

    On the likelihood that one unknown probability exceeds another in view of the evidence of two samples

    William R Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25 0 (3-4): 0 285--294, 1933

    1933

  34. [42]

    Achieving privacy in the adversarial multi-armed bandit

    Aristide CY Tossou and Christos Dimitrakakis. Achieving privacy in the adversarial multi-armed bandit. In Thirty-First AAAI Conference on Artificial Intelligence, 2017

    2017

  35. [43]

    Optimal learning policies for differential privacy in multi-armed bandits

    Siwei Wang and Jun Zhu. Optimal learning policies for differential privacy in multi-armed bandits. Journal of Machine Learning Research, 25 0 (314): 0 1--52, 2024

    2024

  36. [44]

    Locally differentially private (contextual) bandits learning

    Kai Zheng, Tianle Cai, Weiran Huang, Zhenguo Li, and Liwei Wang. Locally differentially private (contextual) bandits learning. In Advances in Neural Information Processing Systems, volume 33, pages 12300--12310, 2020 a

    2020

  37. [45]

    Locally differentially private (contextual) bandits learning

    Kai Zheng, Tianle Cai, Weiran Huang, Zhenguo Li, and Liwei Wang. Locally differentially private (contextual) bandits learning. In Advances in Neural Information Processing Systems, volume 33, pages 12300--12310, 2020 b

    2020

  38. [46]

    Optimal PAC multiple arm identification with applications to crowdsourcing

    Yuan Zhou, Xi Chen, and Jian Li. Optimal PAC multiple arm identification with applications to crowdsourcing. In International Conference on Machine Learning, pages 217--225. PMLR, 2014

    2014

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.