Q1 [partially_resolved] Q1. Is it possible to derive matching upper and lower bounds on regret, for linear contextual bandits, under JDP and adversarial contexts? | remains open: For adversarial (arbitrary) contexts with private contexts and rewards, either give an (ε,δ)-JDP algorithm whose privacy cost is o(√T) (ideally polylog(T)·poly(d)/ε) or prove an Ω(√(T/ε))-type lower bound that separates adversarial from stochastic contexts; the exact poly(d) dependence is also unmat
Q2 [partially_resolved] Q2. Is JDP achievable for free in this setting? | remains open: Determine whether JDP can be achieved with o(√T) (ideally polylog(T)/ε) additional regret when contexts are chosen adversarially and are themselves private, or prove that a √(T/ε)-type price is unavoidable for adversarial contexts.
Q3 [partially_resolved] Q3. If not, what is the minimal set of assumptions on context generation to achieve JDP for free? (Section 3 elaboration: under which conditions on the context generation, i.e. stochastically generated, and with or without margin/diversity conditions, is it possible to achieve JDP for free?) | remains open: Determine whether the i.i.d.-stochastic-context assumption can be weakened (e.g., to oblivious/adaptive adversarial contexts, smoothed or non-stationary context sequences) while keeping the privacy cost at polylog(T)·poly(d)/ε, or prove that stochasticity is necessary—i.e., establish minimality, not
S1 [open] Section 3 (upper bound): Is it possible to propose a JDP variant of LinUCB such that the price of JDP is negligible for adversarial contexts? Can AdaC-OFUL be adapted to private and adversarial contexts with a negligible cost in the regret?
S2 [partially_resolved] Section 3 (lower bound): Can the JDP lower bound of He et al. (2022), Ω(√(dT log K) + d/(ε+δ)), be improved by plugging sharper estimation lower bounds under JDP? Is it possible to provide a regret lower bound under JDP using the KL techniques of Azize and Basu (2022, 2024)? | remains open: Prove (or rule out) a JDP regret lower bound for adversarially chosen private contexts of order √(T/ε) or larger—i.e., one that separates adversarial from stochastic contexts—and pin down the exact poly(d) dependence of the privacy term (d vs d^{3/2}) in the stochastic case.