Research map / Bandits and online learning / Multi-armed bandits
An Optimal Private Stochastic-MAB Algorithm based on Optimal Private Stopping Rule
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use DP Successive Elimination instead of DP-UCB | Private stochastic multi-armed bandits · Tested settings C1-C4 | average pseudo-regret: at least 5 times | Helped |
| Partition arm pulls into geometrically increasing epochs and reset estimates between epochs | DP Successive Elimination · Stochastic K-armed MAB | expected pseudo-regret: O \left( \left(\sum\limits_{a\neq a^*} \frac{\log(T)}{\Delta_{a}}\right) + \frac{K\log(T)}{\varepsilon} \right) | Helped |
| Check stopping conditions at exponentially increasing sample intervals (ablation) | DP-NAS · Private stopping rule | sample complexity: no more than a constant factor | No clear effect |
| Use a simpler private stopping rule based on sparse vector rather than tree-based continual release | Private stochastic multi-armed bandits · Stochastic K-armed MAB | added pseudo-regret: O(\nicefrac{K\log(T)}\varepsilon) | Helped |
Closest papers by meaning
- Fixed-Budget Differentially Private Best Arm Identification (ICLR 2024 · similarity 0.88)
- On the Asymptotic Optimality of Confidence Interval Based Algorithms for Fixed Confidence MABs (AAAI 2025 · similarity 0.88)
- Asymptotically Optimal Best Arm Identification with Fixed-Budget under Differential Privacy (NeurIPS 2026 · similarity 0.87)
- Optimal Algorithm for Max-Min Fair Bandit (ICML 2025 · similarity 0.87)
- Combinatorial Stochastic-Greedy Bandit (AAAI 2024 · similarity 0.87)
- Locally Private and Robust Multi-Armed Bandits (NeurIPS 2024 · similarity 0.86)
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.