Research map / Bandits and online learning / Multi-armed bandits

Shuffle and Joint Differential Privacy for Generalized Linear Contextual Bandits

NeurIPS 2026 · Bandits and online learning › Multi-armed bandits · approach: Optimal stochastic bandit algorithms · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Gives the first shuffle-DP and joint-DP algorithms for generalized linear contextual bandits, using private convex optimization and privatized design matrices, with regret bounds that are order-wise worse than non-private GLM bandits by roughly sqrt(d)/eps (shuffle) and 1/eps (joint).

Problem

Contextual bandits under differential privacy have only been studied for linear rewards with closed-form estimators; generalized linear models lack closed-form estimators and need private convex optimization, and privacy must be maintained across policy switches and the design matrix.

Approach

Extends private linear contextual bandit methods to GLMs by running a shuffle-private convex optimizer for the parameter estimate, tracking privacy of the privatized design matrix, and (for joint DP) accounting for leakage at policy switches via the set of revealed arms, with a batched/phased structure.

Key results

• Shuffle-DP GLM bandit with stochastic contexts: dominant regret about sqrt(T/kappa*) d^{3/2} poly(R,S), which is about sqrt(d)/eps order-wise worse than the non-private SDSB24 bound (up to poly terms and log T), per the authors' rebuttal.
• Joint-DP algorithm: dominant regret about d sqrt(T/eps) poly(R,S), about 1/eps order-wise worse than the non-private counterpart, per the authors' rebuttal.
• Amortized per-step computation is O(log log T) for the shuffle algorithm and O~(log^2 T) for the joint-DP algorithm.

Limitations

• No lower bound for GLM private bandits, so near-optimality is not established; the authors retracted the claim of near-optimality.
• Relies on fixed batching that requires knowledge of horizon T; not anytime.
• Requires an upper bound on kappa (or lower bound on the parameter norm); no empirical experiments in the submission.

Experimental setup

Metrics: regret

Baselines: CZ22 TKMS21 SDSB24

Builds on: shuffle differential privacy for linear contextual bandits [CZ22] SDSB24 generalized linear bandits matrix Chernoff bounds G-optimal design

Closest papers by meaning

• Generalized Linear Bandits with Local Differential Privacy (NeurIPS 2021 · similarity 0.93)
• Optimal Regret of Bandits under Differential Privacy (NeurIPS 2025 · similarity 0.91)
• On Differentially Private Federated Linear Contextual Bandits (ICLR 2024 · similarity 0.91)
• Faster Rates for Private Adversarial Bandits (ICML 2025 · similarity 0.91)
• Connecting Thompson Sampling and UCB: Towards More Efficient Trade-offs Between Privacy and Regret (ICML 2025 · similarity 0.90)
• Generalized Linear Bandits with Limited Adaptivity (NeurIPS 2024 · similarity 0.89)