Reproduce “On First-Order Bounds, Variance and Gap-Dependent Bounds for Adversarial Bandits” on OpenResearch

About this paper

Roman Pogodin, Tor Lattimore

The paper studies adversarial bandits, where a learner observes only the chosen action’s loss and develops INF variants that combine a log barrier with adaptive learning rates while retaining unbiased estimates. One variant achieves first-order expected regret with logarithmic factors and limsup at most 9.2. They also show quadratic variance in two-arm fixed-rate FTRL and expected logarithmic regret under gaps.

Key insights

• It is possible to achieve both first-order regret bounds (dependent on optimal arm loss) and minimax optimal worst-case performance in adversarial bandits using modified FTRL, without altering loss estimators.
• Many standard FTRL algorithms (e.g., Exp3, INF) with importance-weighted estimators suffer from a fundamental limitation: their regret variance can grow quadratically ({Ω}(n{²})) with the horizon.
• Algorithms can adapt to and exploit 'gap' structures in adversarial environments to achieve significantly better, even logarithmically-growing, regret bounds, extending capabilities previously mostly seen in stochastic settings.

Summary by alphaXiv.