Pith. sign in

REVIEW 2 major objections 4 minor 27 references

Connecting Thompson Sampling and UCB: Towards More Efficient Trade-offs Between Privacy and Regret

T0 review · 2 major / 4 minor · reviewed 2026-08-16 · deepseek-v4-flash

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

Pith's one-line read DP-TS-UCB trades privacy and regret with a single parameter, reaching $\tilde{O}(T^{0.25})$-GDP without losing near-optimal regret.

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

arxiv 2505.02383 v2 pith:AIKKDYAK submitted 2025-05-05 cs.LG

Bingshan Hu , Zhiming Huang , Tianyue H. Zhang , Mathias Lécuyer , Nidhi Hegde This is my paper · ORCID
classification cs.LG
keywords differentialprivacystochasticbanditsThompsonSamplingGaussianUpperConfidenceBoundregretboundsprivacy-regrettrade-offanti-concentration
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

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

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

Reading between the lines

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

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

2 major / 4 minor

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.

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 (2)
  1. [Section 4.3, proof of Theorem 4.4] 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.
  2. [Section 4.3, proof of Theorem 4.4] 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.
minor comments (4)
  1. [Section 1 and Section 6] 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.
  2. [Table 1, DP-TS-UCB (α=1) row] 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.
  3. [Appendix B, proof of Lemma 4.1] 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.
  4. [Section 4.3, Theorem 4.4] 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.

Circularity Check

0 steps flagged · score 1.0 of 10

No circular derivation found: the GDP bound is a direct consequence of the chosen sampling budget and an external per-round GDP lemma; self-citations to the epoch structure are not load-bearing.

full rationale

The main derivation chain is self-contained and does not reduce to its inputs by construction. Lemma 4.1 proves the optimism of the maximum of phi Gaussian draws from anti-concentration bounds; Theorem 4.2 derives regret from concentration bounds and a TS/UCB decomposition; Theorem 4.4 derives the GDP guarantee by composing a per-round GDP bound with the GDP composition theorem of Dong et al. (2022), using the epoch structure to ensure a single changed observation enters only one Gaussian distribution from which at most phi samples are drawn. The claim that phi = c0 T^{0.5(1-alpha)} ln^{0.5(3-alpha)}(T) leads to a GDP guarantee of order T^{0.25(1-alpha)} is an algebraic consequence of the chosen parameter, but this is a normal mechanism-design derivation, not a fitted input renamed as a prediction. The per-round privacy input, Lemma 5 of Ou et al. (2024), is an external prior result by non-overlapping authors and is used as a tool rather than as the target claim. The only self-citations are to the arm-specific epoch structure (Hu et al. 2021; Hu & Hegde 2022), and that structure is also described directly in Algorithm 1 (Lines 13-17); these citations are not load-bearing because the no-reuse property is evident from the algorithm itself and is jointly attributed to external prior work as well. One genuine limitation, noted by the skeptical reading, is that the proof of Theorem 4.4 does not explicitly analyze indirect propagation of a changed reward through action-dependent data collection into later epochs; that is a correctness/composition concern about the proof, not a circularity in which a claimed result is equivalent to its inputs. Accordingly, no circular steps are identified and the circularity score is 1.

Assumptions & free parameters 1 free parameters · 6 assumptions · 0 invented entities

The central claims rest on standard tail bounds, GDP composition, one external privacy lemma, and the bounded-reward and known-horizon assumptions. The only hand-chosen quantity is the sampling budget phi. No new physical or mathematical entities are introduced.

free parameters (1)
  • phi (Gaussian sampling budget per epoch) = c0 * T^{0.5(1-alpha)} * ln^{0.5(3-alpha)}(T), with c0 = sqrt(2*pi*e)
    Chosen by the designers to make Lemma 4.1 hold (exploration probability >= 1-O(1/T)) while keeping the GDP composition of phi samples at the desired rate. It is a hand-tuned quantity, not derived from first principles or fitted to data, and the central privacy and regret bounds both depend on it.
assumptions (6)
  • standard math Fact A.3: Gaussian concentration and anti-concentration bounds (Equations 4 and 5).
    Used in the proofs of Lemma 4.1 and Lemma C.1 to bound the probability that a Gaussian posterior sample exceeds or falls below its mean; standard tail bounds.
  • standard math Fact A.2: Hoeffding's inequality.
    Used in Lemmas D.2 and C.1 to bound deviations of the empirical mean from the true mean; standard for bounded rewards.
  • standard math GDP composition theorem and post-processing theorem (Theorems 4.7, 4.8 from Dong et al., 2022).
    Invoked in the proof of Theorem 4.4 to compose the privacy loss over phi rounds and to argue that the max of private samples remains private.
  • domain assumption Lemma 5 of Ou et al. (2024): a single sample from N(mu_hat, sigma^2) has GDP parameter bounded by the sensitivity divided by the noise scale.
    Used without proof in the proof of Theorem 4.4 to assert that each round's Gaussian sample from N(mu_hat, ln^alpha(T)/n_i) is sqrt(1/ln^alpha(T))-GDP; the paper does not re-derive this for the scaled variance.
  • domain assumption Reward distributions have support [0,1] and the optimal arm is unique (Section 2.1).
    Used to apply Hoeffding's inequality and to set the sensitivity of the empirical mean to 1/n_i; standard in the bandit literature.
  • domain assumption The learning horizon T and trade-off parameter alpha are known in advance; the algorithm is not anytime.
    The algorithm sets phi based on T and alpha (Algorithm 1, Line 1), and the analysis covers a fixed horizon. The conclusion acknowledges this limitation, noting that anytime behavior is lost.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Connecting Thompson Sampling and UCB: Towards More Efficient Trade-offs Between Privacy and Regret." pith.science (2026). https://pith.science/paper/AIKKDYAK

@misc{pith2026250502383,
  author       = {Pith},
  title        = {Pith review of: Connecting Thompson Sampling and UCB: Towards More Efficient Trade-offs Between Privacy and Regret},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/AIKKDYAK}},
  note         = {Machine review of arXiv:2505.02383}
}
abstract

We address differentially private stochastic bandit problems from the angles of exploring the deep connections among Thompson Sampling with Gaussian priors, Gaussian mechanisms, and Gaussian differential privacy (GDP). We propose DP-TS-UCB, a novel parametrized private bandit algorithm that enables to trade off privacy and regret. DP-TS-UCB satisfies $ \tilde{O} \left(T^{0.25(1-\alpha)}\right)$-GDP and enjoys an $O \left(K\ln^{\alpha+1}(T)/\Delta \right)$ regret bound, where $\alpha \in [0,1]$ controls the trade-off between privacy and regret. Theoretically, our DP-TS-UCB relies on anti-concentration bounds of Gaussian distributions and links exploration mechanisms in Thompson Sampling-based algorithms and Upper Confidence Bound-based algorithms, which may be of independent interest.

Figures

Figures reproduced from arXiv: 2505.02383 by the authors.

Figure 1
Figure 1. Cap the number of mean reward models sampled from a Gaussian distribution. Assume arm i is pulled in rounds t, t ′ and t ′′, and ϕ = 4. In each of the rounds t + 1, . . . , t + h, . . . , t+ϕ, DP-TS-UCB samples a Gaussian mean reward model θ h i and uses it in the learning for arm i. In each of the rounds t+ϕ+ 1, t+ϕ+ 2, . . . , t′ , DP-TS-UCB reuses the highest model value θ 3 i = maxh∈[ϕ] θ h i among the previousl… view at source ↗
Figure 2
Figure 2. Arm-specific epoch structure. The dashed lines par￾tition rounds from t1 to t12 into three epochs. Assume arm i is pulled in round t1, then we compute its empirical mean as µˆi = X1 at the end of round t1 and arm i’s first epoch ends in round t1. If arm i is pulled in rounds t3, t4 again, then we compute its empir￾ical mean as µˆi = (X3 + X4)/2 at the end of round t4 and arm i’s second epoch ends in round t4. It is … view at source ↗
Figure 3
Figure 3. DP-TS-UCB’s privacy vs regret with different α and T. The setup consists of five arms with Bernoulli rewards. We set the mean rewards as [0.95, 0.75, 0.55, 0.35, 0.15]. We first analyze DP-TS-UCB’s privacy and regret across differ￾ent values of α and T. Then, we compare DP-TS-UCB with M-TS-Gaussian (Ou et al., 2024) from two perspectives: 7 [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗
Figures from the paper (4 more)
Figure 4
Figure 4. Figure 4: The performance of DP-TS-UCB and M-TS-Gaussian under the same theoretical regret bound. outperforming M-TS-Gaussian, as shown in [PITH_FULL_IMAGE:figures/full_fig_p008_4.png]
Figure 5
Figure 5. Figure 5: The regret of DP-TS-UCB and M-TS-Gaussian under the same privacy guarantee with α = 0 and α = 1. TS-UCB is not anytime and achieves only O( √ KT ln T) worst-case regret bounds. If we know the maximum mean reward gap ∆max = maxi∈[K] ∆i in advance, by slightly modifying …
Figure 6
Figure 6. Figure 6: The regret of M-TS-Gaussian with parameters b = {0, 1, 500, 1000, 2000, 5000, 100000} under two privacy guarantees. We can observe that when α = 0, M-TS-Gaussian achieves the lowest regret with b = 1 and c = 1.18, as shown in [PITH_FULL_IMAGE:figures/full_fig_p021_6.png]
Figure 7
Figure 7. Figure 7: The regret of DP-TS-UCB and M-TS-Gaussian under the same privacy guarantee with α = 0 and 1, with comparison to (ϵ, 0)-DP algorithms. We can see that when α = 0, both DP-TS-UCB and M-TS-Gaussian perform better than the (ϵ, 0)-DP algorithms, as shown in [PITH_FULL_IMAG…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

27 extracted references · 21 canonical work pages

  1. [1]

    and Goyal, N

    Agrawal, S. and Goyal, N. N ear-optimal regret bounds for T hompson S ampling. http://www.columbia.edu/ sa3305/papers/j3-corrected.pdf, 2017

    work page 2017

  2. [2]

    Tuning bandit algorithms in stochastic environments

    Audibert, J.-Y., Munos, R., and Szepesv \'a ri, C. Tuning bandit algorithms in stochastic environments. In International conference on algorithmic learning theory, pp.\ 150--165. Springer, 2007

    work page 2007

  3. [3]

    and Ortner, R

    Auer, P. and Ortner, R. UCB revisited: Improved regret bounds for the stochastic multi-armed bandit problem. Periodica Mathematica Hungarica, 61 0 (1-2): 0 55--65, 2010

    work page 2010

  4. [4]

    Finite-time analysis of the multi-armed bandit problem

    Auer, P., Cesa-Bianchi, N., and Fischer, P. Finite-time analysis of the multi-armed bandit problem. Machine learning, 47: 0 235--256, 2002

    work page 2002

  5. [5]

    and Basu, D

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

    work page 2022

  6. [6]

    From optimality to robustness: Adaptive re-sampling strategies in stochastic bandits

    Baudry, D., Saux, P., and Maillard, O.-A. From optimality to robustness: Adaptive re-sampling strategies in stochastic bandits. Advances in Neural Information Processing Systems, 34: 0 14029--14041, 2021

    work page 2021

  7. [7]

    and Jun, K.-S

    Bian, J. and Jun, K.-S. Maillard sampling: B oltzmann exploration done optimally. In International Conference on Artificial Intelligence and Statistics, pp.\ 54--72. PMLR, 2022

    work page 2022

  8. [8]

    Dong, J., Roth, A., and Su, W. J. Gaussian differential privacy. Journal of the Royal Statistical Society Series B: Statistical Methodology, 84 0 (1): 0 3--37, 2022

    2022

Show all 27 references
  1. [9]

    The algorithmic foundations of differential privacy

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

    2014

  2. [10]

    and Capp \'e , O

    Garivier, A. and Capp \'e , O. The KL-UCB algorithm for bounded stochastic bandits and beyond. In Proceedings of the 24th annual conference on learning theory, pp.\ 359--376. JMLR Workshop and Conference Proceedings, 2011

    2011

  3. [11]

    and Takemura, A

    Honda, J. and Takemura, A. An asymptotically optimal bandit algorithm for bounded support models. In COLT, pp.\ 67--79. Citeseer, 2010

    2010

  4. [12]

    and Takemura, A

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

    2015

  5. [13]

    and Hegde, N

    Hu, B. and Hegde, N. N ear-optimal T hompson S ampling-based algorithms for differentially private stochastic bandits. In Uncertainty in Artificial Intelligence, pp.\ 844--852. PMLR, 2022

    2022

  6. [14]

    Hu, B., Huang, Z., and Mehta, N. A. Near-optimal algorithms for private online learning in a stochastic environment. arXiv preprint arXiv:2102.07929, 2021

    2021 arXiv

  7. [15]

    MOTS : M inimax optimal T hompson S ampling

    Jin, T., Xu, P., Shi, J., Xiao, X., and Gu, Q. MOTS : M inimax optimal T hompson S ampling. In International Conference on Machine Learning, pp.\ 5074--5083. PMLR, 2021

    2021

  8. [16]

    Finite-time regret of T hompson S ampling algorithms for exponential family multi-armed bandits

    Jin, T., Xu, P., Xiao, X., and Anandkumar, A. Finite-time regret of T hompson S ampling algorithms for exponential family multi-armed bandits. Advances in Neural Information Processing Systems, 35: 0 38475--38487, 2022

    2022

  9. [17]

    T hompson S ampling with less exploration is fast and optimal

    Jin, T., Yang, X., Xiao, X., and Xu, P. T hompson S ampling with less exploration is fast and optimal. 2023

    2023

  10. [18]

    On Bayesian upper confidence bounds for bandit problems

    Kaufmann, E., Capp \'e , O., and Garivier, A. On Bayesian upper confidence bounds for bandit problems. In Artificial intelligence and statistics, pp.\ 592--600. PMLR, 2012 a

    2012

  11. [19]

    T hompson S ampling: A n asymptotically optimal finite-time analysis

    Kaufmann, E., Korda, N., and Munos, R. T hompson S ampling: A n asymptotically optimal finite-time analysis. In Algorithmic Learning Theory: 23rd International Conference, ALT 2012, Lyon, France, October 29-31, 2012. Proceedings 23, pp.\ 199--213. Springer, 2012 b

    2012

  12. [20]

    Refining the confidence level for optimistic bandit strategies

    Lattimore, T. Refining the confidence level for optimistic bandit strategies. The Journal of Machine Learning Research, 19 0 (1): 0 765--796, 2018

    2018

  13. [21]

    and Thakurta, A

    Mishra, N. and Thakurta, A. (Nearly) optimal differentially private stochastic multi-arm bandits. In Proceedings of the Thirty-First Conference on Uncertainty in Artificial Intelligence, pp.\ 592--601, 2015

    2015

  14. [22]

    A., and Cummings, R

    Ou, T., Medina, M. A., and Cummings, R. Thompson sampling itself is differentially private, 2024. URL https://arxiv.org/abs/2407.14879

    2024 arXiv

  15. [23]

    and Honda, J

    Riou, C. and Honda, J. Bandit algorithms based on Thompson Sampling for bounded reward distributions. In Algorithmic Learning Theory, pp.\ 777--826. PMLR, 2020

    2020

  16. [24]

    and Sheffet, O

    Sajed, T. and Sheffet, O. An optimal private stochastic-mab algorithm based on optimal private stopping rule. In International Conference on Machine Learning, pp.\ 5579--5588. PMLR, 2019

    2019

  17. [25]

    and Sheffet, O

    Shariff, R. and Sheffet, O. Differentially private contextual linear bandits. Advances in Neural Information Processing Systems, 31, 2018

    2018

  18. [26]

    and Zhu, J

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

    2024

  19. [27]

    write newline

    " write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 gl...

Pith tools

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