Research map / Bandits and online learning / Online convex optimization and games
Faster Rates for Private Adversarial 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.
Converts any non-private bandit algorithm into an epsilon-differentially private adversarial bandit algorithm via batching and Laplace noise on batched losses, and builds private EXP4-style algorithms for bandits with expert advice.
Problem
Private adversarial bandits and bandits with expert advice: existing private algorithms have regret O(sqrt(KT log K)/eps) and are local-DP, becoming vacuous for eps <= 1/sqrt(T); no sublinear regret known for small eps.
Approach
Batch losses into blocks of size tau, average them, add Laplace noise of scale 1/(tau eps) to batched losses, and feed to a non-private bandit algorithm that tolerates unbounded negative losses (e.g., HTINF); this reduces noise by the batch factor and gives central DP, plus a batched, privatized EXP4 for experts.
Key results
- Conversion yields epsilon-DP adversarial bandit algorithms with regret O(sqrt(KT)/sqrt(eps)), improving on O(sqrt(KT log(KT))/eps) for all eps <= 1 and giving sublinear regret for eps in omega(1/T).
- Bandits with expert advice: three private algorithms with regret O(sqrt(NT)/sqrt(eps)), O(sqrt(KT log N) log(KT)/eps), and O(N^{1/6}K^{1/2}T^{2/3}log(NT)/eps^{1/3} + sqrt(N) log(NT)/eps), the last sublinear even at eps=1/sqrt(T) when N >= T^{1/4}.
- A lower-bound argument shows that EXP3 and its batched variants cannot achieve an additive separation in eps and T, implying Omega(sqrt(T/eps)) regret for that class.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Convert a non-private bandit algorithm using batched losses and Laplace noise | Adversarial bandits · Adversarial bandits | expected regret upper bound: O\left(\frac{\sqrt{KT\log(KT)}}{\varepsilon}\right) -> O\left(\frac{\sqrt{KT}}{\sqrt{\varepsilon}}\right) | Helped |
| Use the private conversion with HTINF | Bandits with expert advice · Bandits with expert advice | expected regret upper bound: O\left(\frac{\sqrt{NT}}{\sqrt{\varepsilon}}\right) | Helped |
| Add independent Laplace noise to each observed loss in EXP4 | EXP4 · Bandits with expert advice | expected regret upper bound: O\left(\frac{\sqrt{KT\log(N)}\log(KT)}{\varepsilon}\right) | Mixed |
| Batch EXP4 losses and add Laplace noise to expert loss estimates | EXP4 · Bandits with expert advice | expected regret upper bound: \tilde{O}\left(\frac{N^{1/6}K^{1/2}T^{2/3}\log(NT)}{\varepsilon^{1/3}} + \frac{N^{1/2}\log(NT)}{\varepsilon}\right) | Helped |
| Use the private, batched EXP4 guarantee in the high-dimension, high-privacy regime | Private, Batched EXP4 · Bandits with expert advice; N ≥ T^{1/4}, ε = \frac{1}{\sqrt{T}} | regret growth | Helped |
Surprising findings
- A claimed O(T^{2/3}sqrt(K ln K)/eps^{1/3}) bound from prior work could not be verified by the authors.
- Privatizing EXP3 directly is hard because its importance-weighted estimators make per-round privacy loss grow with T.
Limitations
- Expert-advice upper bounds become vacuous when eps <= 1/sqrt(T) and N >= T.
- Guarantees hold only for oblivious adversaries; privacy holds against adaptive adversaries but utility does not.
- Results are worst-case theoretical bounds with no experiments.
Experimental setup
Metrics: expected worst-case regret (theoretical bound)
Baselines: EXP3-based local DP bandit (Tossou and Dimitrakakis / Shariff and Sheffet style) Locally private EXP4 FTRL-based private bandit (Azize and Basu)
Builds on: EXP3 EXP4 HTINF batched bandits
Closest papers by meaning
- Tight First- and Second-Order Regret Bounds for Adversarial Linear Bandits (NeurIPS 2020 · similarity 0.91)
- Achieving Privacy in the Adversarial Multi-Armed Bandit (AAAI 2017 · similarity 0.91)
- Shuffle and Joint Differential Privacy for Generalized Linear Contextual Bandits (NeurIPS 2026 · similarity 0.91)
- Near-Optimal Regret in Adversarial Kernel Bandits (NeurIPS 2026 · similarity 0.90)
- Tracking The Best Expert Privately (ICML 2025 · similarity 0.89)
- Taming Heavy-Tailed Losses in Adversarial Bandits and the Best-of-Both-Worlds Setting (NeurIPS 2024 · similarity 0.89)
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.