Reproduce “uniINF: Best-of-Both-Worlds Algorithm for Parameter-Free Heavy-Tailed MABs” 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
Yu Chen, Jiatai Huang, Yan Dai, Longbo Huang
The `uniINF` algorithm is introduced to tackle Heavy-Tailed Multi-Armed Bandits (HTMABs) by operating without requiring prior knowledge of heavy-tail parameters (σ, α) while achieving nearly optimal regret. It is the first parameter-free algorithm to demonstrate the Best-of-Both-Worlds property, performing effectively in both stochastic and adversarial environments.
Key insights
- A refined log-barrier analysis with a precise bound on Bregman divergence, incorporating an (1 - x_t,i)^2 term, enables effective isolation of sub-optimal arm selections for strong regret guarantees.
- The dynamic learning rate and adaptive loss handling (skipping and clipping) are critical for `uniINF` to maintain robust performance across varying heavy-tailed distributions and environment types.
- Leveraging the truncated non-negative loss assumption for the optimal arm is key to controlling the skipping error, simplifying the overall regret analysis and contributing to BoBW performance.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.