Research map / Bandits and online learning / Multi-armed bandits
Locally Private and Robust Multi-Armed Bandits
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.
Studies locally differentially private, Huber-corrupted, heavy-tailed mean estimation and multi-armed bandits, giving tight minimax rates for the LDP-then-corruption (LTC) and corruption-then-LDP (CTL) orderings and a unified truncation/random-response estimator.
Problem
Mean estimation and multi-armed bandits (online regret and offline sub-optimality) under local differential privacy, Huber corruption, and heavy-tailed rewards, where the order of privacy and corruption matters.
Approach
Shows that the order of LDP and Huber corruption matters: LTC incurs an extra 1/eps factor in the corruption term versus CTL. A single truncation + random rounding + random response estimator is shown to be minimax-optimal for both orders (and C-LDP-C), and is plugged into UCB (online) and LCB (offline) algorithms.
Key results
- Minimax mean-estimation error under LTC is Theta((alpha/eps)^(1-1/k) + ...) versus Theta(alpha^(1-1/k) + ...) under CTL, so LTC is strictly harder by a 1/eps factor in the corruption term.
- Proposes UCB-based online algorithm with almost tight regret (up to log factor), e.g. Omega(T^(3/4)) lower bound for k=2 under LDP heavy tails, showing the prior O(sqrt(T)) upper bound of Tao et al. 2022 is incorrect.
- Offline LCB-based algorithm achieves sub-optimality matching lower bounds up to log factors for both LTC and CTL when beta* >= 2.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Move corruption from before LDP to after LDP | Locally private mean estimation · Mean estimation | minimax high-probability error: α^{1−1/k} -> (α/ε)^{1−1/k} | Hurt |
| Move corruption from before LDP to after LDP | Locally private online MAB · Online MAB | minimax clean regret: T · α^{1−1/k} -> T · (α/ε)^{1−1/k} | Hurt |
| Move corruption from before LDP to after LDP | Locally private offline MAB · Offline MAB | minimax expected sub-optimality: α^{1−1/k} -> (α/ε)^{1−1/k} | Hurt |
| Use Algorithm 2 with the α=0 mean-estimation result and adjust the burn-in period | Locally private heavy-tailed online MAB · Online MAB without corruption | clean regret: O ((K log T/ε²)^{(k−1)/(2k)} T^{(k+1)/(2k)}) | Helped |
| Use LTC rather than CTL corruption ordering | Unified Algorithm · Mean estimation simulations, strong corruption | estimation error | Hurt |
| Use weak sign-flip corruption instead of strong corruption | Mean estimation algorithms · Mean estimation simulations | estimation error | Helped |
| Use weak, non-adversary corruption rather than strong Huber corruption | Algorithm 2 · Online MAB simulations | regret | Helped |
| Use LTC rather than CTL corruption ordering | Algorithm 2 · Online MAB simulations | regret | Hurt |
| Use strong Huber corruption that makes two arm distributions indistinguishable | Algorithm 2 · Online MAB simulations | regret | Hurt |
| Use LTC rather than CTL corruption ordering | Algorithm 3 · Offline MAB simulations | sub-optimality | Hurt |
Surprising findings
- The prior LDP heavy-tailed MAB regret upper bound of Tao et al. (2022) of order sqrt(T) contradicts the lower bound of order T^(3/4) for k=2, so it is ungrounded.
- Replacing random response with the Laplace mechanism in the LTC setting introduces an extra log(1/alpha) factor.
Limitations
- Requires knowledge of the corruption level alpha to set the truncation threshold M; removing this dependence is left open.
- Offline sub-optimality is only tight for beta* >= 2; the good-coverage regime beta* in [1,2) is not characterized.
- Simulations are on synthetic Pareto and adversarial distributions only.
Experimental setup
Metrics: estimation error cumulative regret sub-optimality
Baselines: LDPRSE (Tao et al. 2022) Bubeck et al. 2013 robust MAB algorithm
Builds on: Tao et al. 2022 (LDP heavy-tailed MABs) Ren et al. 2020 (LDP MABs) Wu et al. 2023 (central DP robust MABs) Charisopoulos et al. 2023 (LDP linear bandits under corruption) Rashidinejad et al. 2021 (LCB offline bandits) Bubeck et al. 2013 (heavy-tailed bandits)
Closest papers by meaning
- Corruption-Robust Linear Bandits: Minimax Optimality and Gap-Dependent Misspecification (NeurIPS 2024 · similarity 0.88)
- Nash Social Welfare for Multi Armed Bandits: Trajectory-wise Expected and High Probability Regret (NeurIPS 2026 · similarity 0.88)
- A Near-optimal, Scalable and Parallelizable Framework for Stochastic Bandits Robust to Adversarial Corruptions and Beyond (NeurIPS 2025 · similarity 0.87)
- Stochastic Bandits Robust to Adversarial Attacks (ICLR 2025 · similarity 0.87)
- Faster Rates for Private Adversarial Bandits (ICML 2025 · similarity 0.87)
- Bayesian Regret Minimization in Offline Bandits (ICML 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.