Unverified

What is the Complexity of Joint Differential Privacy in Linear Contextual Bandits?

Fix a horizon $T$ , $K$ available arms, and a feature dimension $d$ . At round $t$ , a context $c_t$ induces

\mathcal{A}_t:=\{\psi(a,c_t):a\in[K]\}\subseteq\mathbb{R}^d, \qquad [K]:=\{1,\ldots,K\},

where $\psi\colon[K]\times\mathcal{C}\to\mathbb{R}^d$ is the feature map. The learner chooses $x_t\in\mathcal{A}_t$ and observes

r_t:=\langle\theta^\star,x_t\rangle+\eta_t,

where $\theta^\star\in\mathbb{R}^d$ is unknown and $\eta_t$ is conditionally $1$ -subgaussian. Contexts may be generated adversarially.

Let

S:=((\mathcal{A}_1,r_1),\ldots,(\mathcal{A}_T,r_T))

and define $S'$ analogously. The two sequences are $t$ -neighbours if $(\mathcal{A}_s,r_s)=(\mathcal{A}'_s,r'_s)$ for every $s\neq t$ . A randomized policy $\pi$ is $(\epsilon,\delta)$ -JDP if, for every $t$ , every pair of $t$ -neighbouring sequences $S,S'$ , and every event $E_{>t}$ of future action sequences,

\Pr\!\left\{\pi_{>t}(S)\in E_{>t}\right\} \leq e^{\epsilon}\Pr\!\left\{\pi_{>t}(S')\in E_{>t}\right\}+\delta,

where $\pi_{>t}(S):=(x_{t+1},\ldots,x_T)$ and the probability is over the policy's randomness. The expected regret is

R_T:=\mathbb{E}\!\left[\sum_{t=1}^T\max_{x\in\mathcal{A}_t} \langle\theta^\star,x-x_t\rangle\right].

Problem 1.

For private rewards and private, adversarially generated contexts, determine matching upper and lower bounds on the regret achievable by $(\epsilon,\delta)$ -JDP policies. In particular, close the gap between the stated upper bound

O\!\left(d\sqrt{T}\log T+d^{3/4}\frac{\sqrt{T\log(1/\delta)}}{\sqrt{\epsilon}}\right)

and lower bound

\Omega\!\left(\sqrt{dT\log K}+\frac{d}{\epsilon+\delta}\right).

Problem 2.

Determine whether JDP is achievable ``for free'' for adversarial contexts, in the sense that the additional regret attributable to privacy is asymptotically negligible in $T$ .

Problem 3.

If such a negligible privacy cost is impossible for adversarial contexts, determine the minimal assumptions on context generation under which it becomes possible, including whether stochastic generation alone suffices or whether additional margin or diversity conditions are needed.

Download

Abstract

Linear contextual bandits with private contexts and rewards are studied under $(\epsilon,\delta)$ -Joint Differential Privacy (JDP), which constrains how changing one round's context--reward data may affect future actions. For adversarial contexts, the best stated regret upper bound is $O\!\left(d\sqrt{T}\log T+d^{3/4}\sqrt{T\log(1/\delta)}/\sqrt{\epsilon}\right)$ , while the stated lower bound is $\Omega\!\left(\sqrt{dT\log K}+d/(\epsilon+\delta)\right)$ . The lower bound already holds for stochastic contexts, leaving a gap in both the horizon dependence and the privacy dependence. The open questions are to obtain matching bounds, determine whether the price of JDP can be asymptotically negligible, and, if not, identify the minimal assumptions on context generation under which such a negligible privacy cost is possible.

Background and progress

For a linear contextual bandit, the context at round $t$ induces a decision set $\mathcal{A}_t\subset\mathbb{R}^d$ ; the learner chooses an action from this set and observes a noisy linear reward. Both the context and reward are private. Shariff and Sheffet introduced JDP for this setting, requiring privacy only for actions taken after the modified round. They also showed that the standard notion of differential privacy applied to the full published action sequence leads to linear regret when both contexts and rewards are private [Shariff and Sheffet, 2018].

Shariff and Sheffet's private LinUCB variant uses a tree-based mechanism to privatize the Gram matrix and reward-weighted action sum. For adversarial contexts, its regret is

O\!\left(d\sqrt{T}\log T+d^{3/4}\frac{\sqrt{T\log(1/\delta)}}{\sqrt{\epsilon}}\right),

so the stated privacy-dependent term is not asymptotically negligible in $T$ [Shariff and Sheffet, 2018]. He, Zhang, and Zhang reduce contextual-bandit regret lower bounds to estimation lower bounds and obtain

\Omega\!\left(\sqrt{dT\log K}+\frac{d}{\epsilon+\delta}\right)

under JDP [He et al., 2022]. Their construction uses stochastic contexts and therefore also gives a lower bound for the adversarial-context setting. The upper and lower bounds do not match in their dependence on $T$ and $\delta$ .

Related private finite-armed and fixed-action linear bandits admit upper and lower bounds matching up to logarithmic factors, with an asymptotically negligible privacy cost under $\rho$ -zCDP [Azize and Basu, 2024]. Azize and Basu obtain this behavior using adaptive, non-overlapping phases, and their AdaC-OFUL algorithm has negligible privacy cost when contexts are public and stochastically generated [Azize and Basu, 2024]. In the contextual problem with private contexts, privately estimating the Gram matrix remains the identified bottleneck. The paper therefore asks whether comparable techniques can handle private adversarial contexts, and, if not, which stochastic, margin, or diversity assumptions on context generation suffice.

Reference papers

Differentially private contextual linear banditsRoshan Shariff, Or SheffetAdvances in Neural Information Processing Systems · 2018
A reduction from linear contextual bandit lower bounds to estimation lower boundsJiahao He, Jiheng Zhang, Rachel ZhangInternational Conference on Machine Learning · 2022
Concentrated differential privacy for banditsAchraf Azize, Debabrota Basu2024 IEEE Conference on Secure and Trustworthy Machine Learning (SaTML) · 2024

What is the Complexity of Joint Differential Privacy in Linear Contextual Bandits?

Problem 1.

Problem 2.

Problem 3.

Coming soon

Organizer