Research map / Bandits and online learning / Multi-armed bandits
Fixed-Budget Differentially Private Best Arm Identification
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 DP-BAI, an epsilon-differentially-private successive-elimination policy for fixed-budget best arm identification in linear bandits, using Max-Det collections and Laplace-noised arm means, with matching-order exponential upper and minimax lower bounds on error probability.
Problem
Fixed-budget best arm identification in linear bandits with rewards in [0,1] under epsilon-differential privacy of the decision policy; prior work covered either fixed-budget BAI without privacy or fixed-confidence BAI with privacy.
Approach
A successive-elimination policy that selects arms via a Max-Det collection (maximum absolute determinant subset) to balance pulls, then privatises each arm's empirical mean with Laplace noise scaled by 1/(epsilon * pulls); also derives an early-stopping-based minimax lower bound on error probability under DP.
Key results
- DP-BAI significantly outperforms Baseline and DP-OD in the synthetic experiment across budgets T and privacy levels epsilon.
- As epsilon grows large, DP-BAI performance approaches that of the non-private OD-LinBAI.
- Upper bound exp(-Omega(T/(H log d))) with H = H_BAI + H_pri, and a minimax lower bound showing the dependence on H_BAI and H_pri is tight in the stated sense.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use Max-Det collections to exploit the linear structure of arm means (ablation) | DP-BAI versus Baseline · Synthetic linear BAI | best-arm identification success rate | Helped |
| use Max-Det collections instead of the DP-OD sampling strategy | DP-BAI versus DP-OD · Synthetic linear BAI | best-arm identification success rate | Helped |
| remove the privacy requirement by taking ε→+∞ | DP-BAI compared with OD-LinBAI · Synthetic linear BAI | best-arm identification success rate | No clear effect |
Surprising findings
- The Gaussian variant DP-BAI-Gauss can give a better exponent than DP-BAI for large delta, but is vacuous at delta=0.
Limitations
- Lower bound is minimax over hard instances, not matching the upper bound for every instance.
- Experiments are limited to one small synthetic instance (K=30, d=2).
- Upper bound has extra log d factor and open question whether an efficient policy matches a problem-dependent lower bound.
Experimental setup
Datasets: synthetic linear bandit instance (K=30, d=2)
Benchmarks: synthetic linear bandit instance
Metrics: fraction of trials identifying best arm (1000 trials)
Baselines: Baseline (DP-BAI without Max-Det collections) OD-LinBAI DP-OD Sequential Halving
Builds on: Sequential Halving OD-LinBAI G-optimal design table-DP
Closest papers by meaning
- Asymptotically Optimal Best Arm Identification with Fixed-Budget under Differential Privacy (NeurIPS 2026 · similarity 0.95)
- Optimal Best Arm Identification under Differential Privacy (NeurIPS 2025 · similarity 0.92)
- Almost Minimax Optimal Best Arm Identification in Piecewise Stationary Linear Bandits (NeurIPS 2024 · similarity 0.90)
- Optimal Multi-Fidelity Best-Arm Identification (NeurIPS 2024 · similarity 0.90)
- Balancing Performance and Costs in Best Arm Identification (NeurIPS 2025 · similarity 0.90)
- On Universally Optimal Algorithms for A/B Testing (ICML 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.