Reproduce “A Further Efficient Algorithm with Best-of-Both-Worlds Guarantees for $m$-Set Semi-Bandit Problem” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Botao Chen, Jongyeong Lee, Chansoo Kim, Junya Honda
An algorithm employing Follow-the-Perturbed-Leader (FTPL) with Fréchet or Pareto-type perturbations achieves Best-of-Both-Worlds guarantees for m-set semi-bandit problems, demonstrating O(sqrt(mdT)) adversarial regret and logarithmic stochastic regret. Its novel Conditional Geometric Resampling (CGR) technique reduces the computational complexity of loss estimation from O(d^2) to O(md(log(d/m) + 1)) per round.
Key insights
- Heavy-tailed Fréchet or Pareto perturbations are essential for FTPL to achieve both minimax optimal adversarial regret and logarithmic stochastic regret in the m-set semi-bandit setting.
- Conditional Geometric Resampling efficiently reduces the expected number of resamples for unbiased loss estimation, resulting in a nearly linear computational complexity in 'd'.
- FTPL offers an optimization-free alternative to FTRL, matching theoretical guarantees while providing practical benefits in computational efficiency and numerical stability.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.