The price of joint differential privacy in linear contextual bandits

Contextual bandits choose recommendations or treatments for a stream of users, and both a user's context and their response are personal data. For linear contextual bandits under joint differential privacy, the best algorithm pays for privacy at the same $\sqrt{T}$ rate as for learning itself, while the best lower bound leaves room for a price that does not grow with $T$ at all. Which is right?

Problem

In each round $t = 1, \dots, T$, the environment reveals a decision set $A_t \subset \mathbb{R}^d$, which may be chosen adversarially; the policy picks $a_t \in A_t$ and observes $r_t = \langle \theta^\star, a_t \rangle + \eta_t$, where $\theta^\star \in \mathbb{R}^d$ is unknown and $\eta_t$ is conditionally 1-subgaussian noise. The regret is

$$R_T = \mathbb{E}\Big[\sum_{t=1}^{T} \max_{a \in A_t} \langle \theta^\star, a - a_t \rangle\Big].$$

Treat round $t$ as the private data $(A_t, r_t)$ of one user. Two sequences of such pairs are $t$-neighbors if they differ only in round $t$. A policy $\pi$ is $(\varepsilon, \delta)$-jointly differentially private (JDP) if for every $t$, every pair of $t$-neighbors $S, S'$ and every set $E$ of action sequences for rounds $t+1, \dots, T$,

$$\Pr[\pi(S) \in E] \le e^{\varepsilon} \Pr[\pi(S') \in E] + \delta .$$

The action at round $t$ itself is not protected; protecting it as well forces linear regret [2].

Question. What is the optimal regret of $(\varepsilon, \delta)$-JDP policies for adversarial contexts, up to logarithmic factors? In particular, is privacy almost free: is there a JDP policy whose regret is the non-private $\widetilde O(d \sqrt{T})$ plus a privacy term that grows only polylogarithmically in $T$?

Background

Shariff and Sheffet introduced joint differential privacy for contextual linear bandits in 2018 and made LinUCB private by releasing noisy running sums with the tree-based mechanism [2]. For bandits without contexts the picture is now sharp. For finite-armed and linear bandits under zero-concentrated differential privacy, the extra regret due to privacy is only polylogarithmic in $T$, and upper and lower bounds match up to logarithmic factors (Azize and Basu, 2024) [4]. Azize and Basu asked at COLT 2024 whether the same holds once contexts are private and adversarial [1].

What is known

• Upper bound. JDP LinUCB has regret $O\big(d\sqrt{T}\log T + d^{3/4}\sqrt{T \log(1/\delta)}/\sqrt{\varepsilon}\big)$ for adversarial contexts (Shariff and Sheffet, 2018) [2]. The privacy term grows like $\sqrt{T}$.
• Lower bound. Every JDP policy has worst-case regret $\Omega\big(\sqrt{dT\log K} + d/(\varepsilon + \delta)\big)$, where $K$ is the number of actions per round (He, Zhang and Zhang, 2022) [3]. It is proved for stochastic contexts and so also holds for adversarial ones.
• Public stochastic contexts. The phased algorithm AdaC-OFUL makes the price of privacy negligible when contexts are public and stochastic [4]. The bottleneck is estimating the Gram matrix of private, adversarial contexts.
• Generalized linear models. A 2026 algorithm for generalized linear contextual bandits under JDP with adversarial contexts again has a privacy term that grows like $\sqrt{T/\varepsilon}$, up to factors polynomial in $d$ and $\log T$ [5].

What would count as progress

• A JDP policy for adversarial contexts with regret $\widetilde O(d\sqrt{T})$ plus a privacy term of order $\mathrm{poly}(d, \log T)/\varepsilon$, with a proof.
• A lower bound showing that, for some adversarial context sequences, every JDP policy pays a privacy term that grows polynomially in $T$.
• Conditions on how contexts are generated (stochastic, with margin or diversity assumptions) under which privacy is provably almost free, with matching lower bounds.

References

1. A. Azize and D. Basu, Open problem: What is the complexity of joint differential privacy in linear contextual bandits?, COLT 2024, PMLR 247 (2024), 5306–5311. PMLR
2. R. Shariff and O. Sheffet, Differentially private contextual linear bandits, NeurIPS (2018). arXiv:1810.00068
3. J. He, J. Zhang and R. Q. Zhang, A reduction from linear contextual bandits lower bounds to estimations lower bounds, ICML 2022, PMLR 162 (2022), 8660–8677. PMLR
4. A. Azize and D. Basu, Concentrated differential privacy for bandits, IEEE SaTML (2024), 78–109. arXiv:2309.00557
5. S. Sarmasarkar, Shuffle and joint differential privacy for generalized linear contextual bandits, preprint (2026). arXiv:2602.00417

Source

Imported from COLT open problems, COLT 2024, curated by the Conference on Learning Theory (COLT). Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.