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

Contextual bandits serve as a theoretical framework to design recommender systems, which often rely on user-sensitive data, making privacy a critical concern. However, a significant gap remains between the known upper and lower bounds on the regret achievable in linear contextual bandits under Joint Differential Privacy (JDP), which is a popular privacy definition used in this setting. In particular, the best regret upper bound is known to be O (d√T log(T) + d³/^4pT log(1/δ)/√ϵ), while the lower bound is Ω (pdT log(K) + d/(ϵ + δ)). We discuss the recent progress on this problem, both from the algorithm design and lower bound techniques, and posit the open questions.