Synapse
⌘+K
Synapse
PulseExploreClubsResearchersJournals
Instagram
HomeClubsExplore
October 1, 2025Open Access

Follow-the-Perturbed-Leader Approaches Best-of-Both-Worlds for the m-Set Semi-Bandit Problems

View Full Paper
Ask AI
Bookmark
Share

Authors

JZJie ZhanXYXin YangCSChenjie Sun

Discussion

Loading...

Member takes

Overview

Adversarial m-set semi-bandit learning demonstrates optimal regret bounds, suggesting efficient strategies in both adversarial and stochastic settings.

Key Points

  • Follow-the-Perturbed-Leader policy achieves near optimal regret bound, improving efficiency in arm selection.
  • The regret bound for FTPL with Fréchet perturbation is shown to be O(sqrt(nm)(sqrt(d log(d)) + m^(5/6))).
  • Lower bounds indicate extra factors in the approach are unavoidable, necessitating innovative methods for improvement.
  • The work establishes best-of-both-world regret bounds, balancing adversarial and stochastic settings effectively.

Cite This Study

Zhan et al. (2025) studied this question.

synapsesocial.com/papers/68dd89e6fe798ba2fc498077https://doi.org/10.48550/arxiv.2504.07307
View Full Paper
Ask AI
Bookmark
Share

Also Consider

Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context:

  1. 1Follow-the-Perturbed-Leader for Decoupled Bandits: Best-of-Both-Worlds and Practicality2025
  2. 2Near-Optimal Regret for Efficient Stochastic Combinatorial Semi-Bandits2025
  3. 3Heavy-tailed Linear Bandits: Adversarial Robustness, Best-of-both-worlds, and Beyond2025
  4. 4Nearly Minimax Optimal Regret for Multinomial Logistic Bandit2024
  5. 5Beyond Primal-Dual Methods in Bandits with Stochastic and Adversarial Constraints2024