Research map / Bandits and online learning / Multi-armed bandits
On the Optimality of Perturbations in Stochastic and Adversarial Multi-armed Bandit Problems
Baekjin Kim, Ambuj Tewari
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (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 Gaussian perturbations with parameter 2 and a matching lower-tail condition | FTPL for stochastic bandits · Stochastic multi-armed bandits | instance-dependent regret: C'' \sum_{\Delta_i>0}\big( {\log(T \Delta_i^2)}/{\Delta_i} + \Delta_i \big) | Improved |
| Use bounded-support perturbations with the prescribed confidence-interval scaling | FTPL for stochastic bandits · Stochastic multi-armed bandits | instance-dependent regret: C''' \sum_{\Delta_i>0}\Big( {\log(T)}/{\Delta_i} + \Delta_i \Big) | Improved |
| Replace deterministic UCB choices with Uniform or Rademacher perturbations and a wider confidence interval | UCB1 · Stochastic multi-armed bandits | regret: same regret bound as that of UCB1 | No clear effect |
| Use bounded perturbations without the extra logarithmic scaling in T | FTPL for stochastic bandits · Two-armed bandit example | regret: linear regret | Hurt |
| Tune Gaussian and Double-exponential FTPL perturbations | FTPL · Simulated stochastic bandits with four reward distributions | average regret | Improved |
| Use UCB1 rather than RCB | UCB1 and RCB · Simulated stochastic bandits with Rademacher rewards | average regret | Hurt |
| Use RCB with Uniform or Rademacher perturbations rather than UCB1 | Randomized Confidence Bound · Simulated stochastic bandits with four reward distributions | average regret | Mixed |
| Seek an exact additive-perturbation equivalent of Tsallis entropy for K >= 4 | FTPL for adversarial bandits · Adversarial K-armed bandits | existence of equivalent choice probabilities: K \ge 4 | Hurt |
| Use Fréchet-type rather than Gumbel-type perturbations | GBPA for adversarial bandits · Adversarial multi-armed bandits | expected block maximum: K^{1/\alpha} | Improved |
Closest papers by meaning
- A Perturbation Approach to Unconstrained Linear Bandits (ICML 2026 · similarity 0.93)
- Stochastic Bandits Robust to Adversarial Attacks (ICLR 2025 · similarity 0.91)
- Improved Best-of-Both-Worlds Regret for Bandits with Delayed Feedback (NeurIPS 2025 · similarity 0.90)
- Follow-the-Perturbed-Leader Nearly Achieves Best-of-Both-Worlds for the m-Set Semi-Bandit Problems (NeurIPS 2025 · similarity 0.90)
- Beyond Primal-Dual Methods in Bandits with Stochastic and Adversarial Constraints (NeurIPS 2024 · similarity 0.90)
- Bayesian Regret Minimization in Offline Bandits (ICML 2024 · similarity 0.90)
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.
