📊 statistics

AdaPrivate-TS: Private Thompson Sampling for Contextual Bandits with Privacy Amplification

AdaPrivate-TS is a differentially private contextual bandit algorithm that leverages the interpretation of privacy noise as increased uncertainty within Thompson Sampling, achieving near-optimal performance with logarithmic privacy costs through batched zCDP composition and privacy amplification.

Original authors: Mohammadreza Riyazat, Eranga Ukwatta

Published 2026-06-23

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Mohammadreza Riyazat, Eranga Ukwatta

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Core Problem: The "Shy Customer" Dilemma

Imagine you run a massive online bookstore. You want to recommend the perfect book to every customer. To do this, you need to learn what they like. But here’s the catch: customers are shy. They don’t want you knowing their exact reading habits because that’s private information.

In the world of computer science, this is called Differential Privacy. It’s a mathematical guarantee that says, "We can learn general trends without knowing exactly what you specifically did."

The problem is that to protect privacy, computers have to add "noise" (random static) to the data. Usually, this noise acts like fog—it confuses the computer, making it worse at recommending books. Most existing algorithms treat this noise as a nuisance, like trying to read a menu through a rainy window.

The Big Insight: Noise is Not Fog, It’s a Hint

The authors of this paper discovered something clever. They looked at a specific recommendation strategy called Thompson Sampling (TS).

Think of Thompson Sampling like a curious explorer. Instead of just picking the book that looks best based on past data, the explorer occasionally picks a random book just to see what happens. This is called "exploration."

The authors realized that when you add privacy noise to the data, it doesn’t just confuse the explorer. Instead, it makes the explorer think, "Hmm, I’m not sure about this book. Maybe I should explore more."

Old Way (UCB): Treats privacy noise as corruption. It’s like the explorer getting dizzy and stumbling around.
New Way (AdaPrivate-TS): Treats privacy noise as uncertainty. It’s like the explorer seeing the fog and deciding, "Since I can’t see clearly, I’ll try a few different paths to be safe."

By interpreting the noise as "I don’t know enough yet," the algorithm actually uses the privacy protection to help it learn better.

How It Works: The "Batched" Strategy

The algorithm, named AdaPrivate-TS, works in two main steps:

Batching (The Weekly Report): Instead of updating its knowledge after every single book click (which would require adding noise every time and getting very messy), the algorithm waits. It collects a batch of interactions (say, 300 clicks) and then adds the privacy noise all at once.
- Analogy: Imagine a teacher grading papers. If they grade one paper at a time and add a random error to each grade, the final average is terrible. But if they grade 300 papers, calculate the average, and then add one small random error to the final average, the result is much more accurate. This is called Parallel Composition. It allows the algorithm to use less noise overall while still keeping privacy high.
Adaptive Exploration (The Confidence Dial): At the start, the algorithm is very unsure, so it explores a lot. As it learns more, it becomes more confident and focuses on recommending the best books. The algorithm automatically adjusts this "confidence dial" over time.

The "Secret Sauce": Privacy Amplification

For users who need extreme privacy (very strict rules), the authors added a technique called Poisson Subsampling.

Analogy: Imagine you want to know the average height of people in a stadium, but you can’t measure everyone. You randomly pick 30% of the people to measure. Because you’re only looking at a small, random slice, it’s even harder for anyone to figure out who was in the stadium. This "amplifies" the privacy.
The algorithm uses this to reduce the amount of noise needed, keeping recommendations accurate even under strict privacy rules.

The Results: It Actually Works

The researchers tested this on synthetic data and real-world datasets (like MovieLens and Jester, which are used to test recommendation systems). Here is what they found:

Better than the Old Way: AdaPrivate-TS performed significantly better than the standard private method (called UCB). In some cases, it was up to 18% better at making good recommendations while keeping the same level of privacy.
Almost as Good as No Privacy: Even with strict privacy settings, the algorithm achieved 93–99% of the performance of a non-private system (a system that sees all your data).
Stable Learning: Unlike other methods that stumble at the beginning when privacy noise is first introduced, AdaPrivate-TS learned smoothly from the start.
Works with Private Features: Even if the features of the items (like the movie’s genre tags) are also privatized, the algorithm still outperforms others by a large margin (+11%).

Why This Matters

This paper shows that we don’t have to choose between privacy and performance. By changing how we interpret the "noise" required for privacy—seeing it as a signal to explore rather than a mistake—we can build recommendation systems that respect user privacy without being dumb or inaccurate.

In short: AdaPrivate-TS turns the "static" of privacy into a useful tool for learning, allowing computers to recommend things to you effectively, even when they are legally required to "forget" the details of your specific behavior.

Technical Summary: AdaPrivate-TS

Problem Statement
Online recommender systems face a fundamental tension between learning user preferences from private behavioral data and providing rigorous privacy guarantees. While Differential Privacy (DP) offers strong protection, the injected noise typically degrades learning performance. Existing private contextual bandit algorithms often treat privacy noise as pure corruption. This paper addresses the challenge of maintaining high utility in contextual bandits under event-level DP, where adjacent datasets differ by a single user-reward pair. The authors argue that previous impossibility results requiring adversarial contexts and joint DP do not apply to stochastic contexts with event-level privacy, allowing for more efficient privacy mechanisms.

Methodology
The authors propose AdaPrivate-TS, a differentially private contextual bandit algorithm that integrates Thompson Sampling (TS) with batched zero-concentrated Differential Privacy (zCDP).

Noise as Posterior Inflation: The core insight is that adding Gaussian noise $\eta \sim \mathcal{N}(0, \sigma^2 I)$ to the sufficient statistics vector $b$ does not merely corrupt the estimate for TS. Instead, it structurally inflates the posterior covariance. Specifically, the sampling distribution becomes $\tilde{\theta}_t \sim \mathcal{N}(\hat{\theta}_t, v^2 A_t^{-1} + \sigma^2 A_t^{-2})$ . TS interprets this inflated covariance as increased uncertainty, thereby converting privacy noise into exploration rather than treating it as error.
Batched Parallel Composition: The algorithm operates in batches of size $B$ . Noise is added to the batched reward sums only at batch boundaries. Because each batch processes disjoint subsets of data, the privacy costs compose in parallel. This ensures the total privacy cost is determined by the maximum cost per batch ( $\rho$ ), rather than summing across all rounds. This allows the privacy cost to be amortized, resulting in a regret bound logarithmic in $T$ .
Privacy Amplification: For stringent privacy budgets ( $\varepsilon \le 1$ ), the method employs Poisson subsampling with rate $q$ . By analyzing the Rényi Differential Privacy (RDP) of the subsampled Gaussian mechanism, the authors show that the effective privacy cost is reduced by a factor related to $q^2$ , allowing for lower noise levels ( $\sigma_{amp} < \sigma_{base}$ ) while maintaining the same $(\varepsilon, \delta)$ guarantee.
Adaptive Exploration: To mitigate excessive early exploration caused by privacy noise, the algorithm decays the exploration parameter $v_k$ geometrically ( $v_k = v_0 \cdot \gamma^{k-1}$ ).

Key Contributions

Theoretical Framework: The paper proves that under event-level DP with stochastic contexts, the privacy cost in the regret bound is $O(\sqrt{d} \cdot \log T / \sqrt{\rho})$ , which is logarithmic in $T$ . This contrasts with the $\tilde{O}(T^{3/4})$ regret under joint DP or $O(\sqrt{d} \cdot \sqrt{T}/\sqrt{\rho})$ under sequential composition.
Privacy Amplification Analysis: The authors provide a rigorous RDP-based analysis of Poisson subsampling for bandits, demonstrating that it can reduce effective noise at low $\varepsilon$ without the sensitivity-rescaling cancellation issues found in standard DP accounting.
Algorithm Design: AdaPrivate-TS replaces UCB with TS in the private bandit framework, leveraging the "noise-as-uncertainty" property to achieve improved regret.

Results
Experiments on synthetic and real-world datasets (MovieLens-25M and Jester) demonstrate the following:

Performance vs. Non-Private Baselines: AdaPrivate-TS achieves 93–99% of non-private performance at $\varepsilon \in [0.5, 5]$ .
Superiority over UCB: AdaPrivate-TS outperforms private UCB (AdaPrivate-UCB) by 0.5–3.7% under default settings. With tuned adaptive exploration, the advantage grows to up to 18% at extreme $\varepsilon$ .
Privacy Amplification Gains: Using Poisson subsampling provides additional 2–5% gains at low $\varepsilon$ (e.g., $\varepsilon=1$ ).
Real-World Dominance: On MovieLens and Jester, AdaPrivate-TS achieves the best overall performance among event-level baselines, particularly dominating at $\varepsilon \ge 2$ .
DP-SVD Features: When features are privatized using DP-SVD, TS’s advantage over UCB increases to +11%, confirming that the noise-as-uncertainty interpretation holds for feature privacy as well.
Stability: Unlike UCB, which suffers an initial CTR drop upon the arrival of the first batch of privacy noise, AdaPrivate-TS shows stable learning dynamics, climbing steadily without significant dips.

Significance
The paper claims that Thompson Sampling is inherently better suited for private contextual bandits than Upper Confidence Bound (UCB) methods because it naturally interprets differential privacy noise as increased posterior uncertainty. By utilizing batched parallel composition, the method achieves a logarithmic privacy cost in $T$ , significantly improving upon existing bounds. The work provides a rigorous theoretical foundation and comprehensive empirical validation, demonstrating that high utility can be maintained under strict event-level privacy constraints without requiring centralized curators or stronger privacy models like joint DP.