← All problems
Unverified
What Is the Complexity of Joint Differential Privacy in Linear Contextual Bandits?
At round , a learner observes a decision set , chooses , and receives
where is unknown and is conditionally sub-Gaussian. Require the future action transcript to be -differentially private with respect to changing one context--reward record (joint differential privacy). Determine matching upper and lower bounds on the regret
for private, adversarial contexts. In particular:
-
Can a jointly private algorithm have only an asymptotically negligible privacy cost?
-
Can adaptive-phased OFUL be adapted to private, adversarial contexts with negligible additional regret?
-
If not, what minimal stochastic, margin, or diversity assumptions on context generation make joint privacy free in this sense?
