← All problems
Unverified

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

At round t≤Tt\leq T, a learner observes a decision set At⊆Rd\mathcal A_t\subseteq\mathbb R^d, chooses at∈Ata_t\in\mathcal A_t, and receives

rt=⟨θ⋆,at⟩+ηt, r_t=\langle\theta^\star,a_t\rangle+\eta_t,

where θ⋆∈Rd\theta^\star\in\mathbb R^d is unknown and ηt\eta_t is conditionally sub-Gaussian. Require the future action transcript to be (ε,δ)(\varepsilon,\delta)-differentially private with respect to changing one context--reward record (joint differential privacy). Determine matching upper and lower bounds on the regret

RT=∑t=1T(max⁡a∈At⟨θ⋆,a⟩−⟨θ⋆,at⟩) R_T=\sum_{t=1}^T\left(\max_{a\in\mathcal A_t}\langle\theta^\star,a\rangle-\langle\theta^\star,a_t\rangle\right)

for private, adversarial contexts. In particular:

  1. Can a jointly private algorithm have only an asymptotically negligible privacy cost?

  2. Can adaptive-phased OFUL be adapted to private, adversarial contexts with negligible additional regret?

  3. If not, what minimal stochastic, margin, or diversity assumptions on context generation make joint privacy free in this sense?

Coming soon

Organizer

Boyuan Wang portraitBoyuan Wang
Minghan Wang portraitMinghan Wang
Bochao Li portraitBochao Li
Hongwei Hu portraitHongwei Hu