Research map / Bandits and online learning / Contextual bandits and Thompson sampling

Responsible Bandit Learning via Privacy-Protected Mean-Volatility Utility

AAAI 2024 · Bandits and online learning › Contextual bandits and Thompson sampling · approach: Practical contextual bandit extensions · 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.

Proposes a privacy-protected responsible bandit objective (mean plus normalized volatility) for two-armed bandits under local differential privacy, with an optimal strategy maximizing the probability the utility falls in an interval, plus a hypothesis test with higher power than the normality test.

Problem

Classical privacy-preserving bandits maximize mean reward and ignore risk/volatility, and normal-based tests on privacy-protected bandit data are unreliable (inflated Type I error, low power) at limited sample sizes.

Approach

Introduces a mean-volatility utility (average reward plus accumulated normalized volatility) under local differential privacy (Laplace, Bernoulli, Gaussian mechanisms), an optimal recursive arm-selection strategy that maximizes the probability the utility falls in a target interval, and uses its asymptotic distribution for sequential hypothesis testing.

Key results

• Under Laplace, Bernoulli, and Gaussian LDP mechanisms the convergence rates to the maximal interval probability are O(1/(eps*sqrt(n))), O(1/(e^eps+1)), and O(sqrt(ln(1/delta))/(eps*sqrt(n))) respectively.
• Simulations with n=500 replicates show empirical rejection rates near the nominal 0.05 level (e.g., 0.048-0.062) under the proposed test across Laplace, Bernoulli, and Gaussian mechanisms with eps=0.5 and 1.
• Simulation power curves report the proposed test outperforms the normality test under the Laplace mechanism, with the advantage growing as privacy noise increases.

Measured effects reported in the paper

Surprising findings

• The Bernoulli mechanism changes the asymptotic limiting distribution itself rather than only the convergence rate, and as eps decreases the interval probability decreases.
• The paper notes that the optimal strategy as defined makes the limiting interval probability equal to the Gaussian-based bound only when d1 = 0, so the gain over normality testing depends on arm reward gaps.

Limitations

• Analysis restricted to two-armed bandits with equal arm variances assumed (standardization otherwise).
• Simulations use synthetic reward distributions and assume sigma_epsilon is known.
• Claimed superiority over other bandit algorithms is supported mainly by theoretical rate comparisons rather than experiments against baselines.

Experimental setup

Metrics: probability of utility in interval empirical coverage / Type I error statistical power convergence rate

Baselines: normality test epsilon-greedy

Builds on: Ren et al. 2020 local differential privacy bandit Cui et al. 2023 mean-volatility utility nonlinear central limit theorem (Chen et al.)

Closest papers by meaning

• Generalized Linear Bandits with Local Differential Privacy (NeurIPS 2021 · similarity 0.88)
• Connecting Thompson Sampling and UCB: Towards More Efficient Trade-offs Between Privacy and Regret (ICML 2025 · similarity 0.86)
• Shuffle and Joint Differential Privacy for Generalized Linear Contextual Bandits (NeurIPS 2026 · similarity 0.85)
• Locally Private and Robust Multi-Armed Bandits (NeurIPS 2024 · similarity 0.85)
• Asymptotically Optimal Best Arm Identification with Fixed-Budget under Differential Privacy (NeurIPS 2026 · similarity 0.84)
• Faster Rates for Private Adversarial Bandits (ICML 2025 · similarity 0.84)