# Adversarially Robust Multi-Armed Bandit Algorithm with Variance-Dependent Regret Bounds arXiv: https://arxiv.org/abs/2206.06810 · HTML: https://mlsanity.com/paper/2206.06810/ ## Key facts - Cited by 12 papers in the map (data through 14 Oct 2026). - Builds on 20 of its 42 references that are in the map. - First posted on arXiv 14 Jun 2022. ## Builds on (most cited first, 20 of 20) - [Optimization, Learning, and Games with Predictable Sequences](https://mlsanity.com/paper/1311.1869/) (2013) - [Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Bandits](https://mlsanity.com/paper/1807.07623/) (2018) - [More Adaptive Algorithms for Adversarial Bandits](https://mlsanity.com/paper/1801.03265/) (2018) - [A Second-order Bound with Excess Losses](https://mlsanity.com/paper/1402.2044/) (2014) - [What Doubling Tricks Can and Can't Do for Multi-Armed Bandits](https://mlsanity.com/paper/1803.06971/) (2018) - [Follow the Leader If You Can, Hedge If You Must](https://mlsanity.com/paper/1301.0534/) (2013) - [Beating Stochastic and Adversarial Semi-bandits Optimally and Simultaneously](https://mlsanity.com/paper/1901.08779/) (2019) - [Simultaneously Learning Stochastic and Adversarial Episodic MDPs with Known Transition](https://mlsanity.com/paper/2006.05606/) (2020) - [Achieving Near Instance-Optimality and Minimax-Optimality in Stochastic and Adversarial Linear Bandits Simultaneously](https://mlsanity.com/paper/2102.05858/) (2021) - [An algorithm with nearly optimal pseudo-regret for both stochastic and adversarial bandits](https://mlsanity.com/paper/1605.08722/) (2016) - [An Improved Parametrization and Analysis of the EXP3++ Algorithm for Stochastic and Adversarial Bandits](https://mlsanity.com/paper/1702.06103/) (2017) - [The best of both worlds: stochastic and adversarial episodic MDPs with unknown transition](https://mlsanity.com/paper/2106.04117/) (2021) - [On the optimality of the Hedge algorithm in the stochastic regime](https://mlsanity.com/paper/1809.01382/) (2018) - [Prediction with Corrupted Expert Advice](https://mlsanity.com/paper/2002.10286/) (2020) - [Sparsity, variance and curvature in multi-armed bandits](https://mlsanity.com/paper/1711.01037/) (2017) - [Improved Path-length Regret Bounds for Bandits](https://mlsanity.com/paper/1901.10604/) (2019) - [Connections Between Mirror Descent, Thompson Sampling and the Information Ratio](https://mlsanity.com/paper/1905.11817/) (2019) - [On Optimal Robustness to Adversarial Corruption in Online Decision Problems](https://mlsanity.com/paper/2109.10963/) (2021) - [Improved Analysis of the Tsallis-INF Algorithm in Stochastically Constrained Adversarial Bandits and Stochastic Bandits with Adversarial Corruptions](https://mlsanity.com/paper/2103.12487/) (2021) - [Following the Leader and Fast Rates in Linear Prediction: Curved Constraint Sets and Other Regularities](https://mlsanity.com/paper/1702.03040/) (2017) ## Built on by (most cited first, 12 of 12) - [A Blackbox Approach to Best of Both Worlds in Bandits and Beyond](https://mlsanity.com/paper/2302.09739/) (2023) - [Best-of-Both-Worlds Algorithms for Partial Monitoring](https://mlsanity.com/paper/2207.14550/) (2022) - [Stability-penalty-adaptive follow-the-regularized-leader: Sparsity, game-dependency, and best-of-both-worlds](https://mlsanity.com/paper/2305.17301/) (2023) - [Best-of-Three-Worlds Linear Bandit Algorithm with Variance-Adaptive Regret Bounds](https://mlsanity.com/paper/2302.12370/) (2023) - [Adaptive Learning Rate for Follow-the-Regularized-Leader: Competitive Analysis and Best-of-Both-Worlds](https://mlsanity.com/paper/2403.00715/) (2024) - [Follow-the-Perturbed-Leader with Fr'echet-type Tail Distributions: Optimality in Adversarial Bandits and Best-of-Both-Worlds](https://mlsanity.com/paper/2403.05134/) (2024) - [Sublogarithmic Swap Regret in Multiplayer General-Sum Games via Hybrid Regularization](https://mlsanity.com/paper/2608.04149/) (2026) - [Asymptotically Optimal Fixed-Budget Best Arm Identification with Variance-Dependent Bounds](https://mlsanity.com/paper/2302.02988/) (2023) - [Exploration by Optimization with Hybrid Regularizers: Logarithmic Regret with Adversarial Robustness in Partial Monitoring](https://mlsanity.com/paper/2402.08321/) (2024) - [Adaptive Experimental Design for Policy Learning](https://mlsanity.com/paper/2401.03756/) (2024) - [Multi-Play Combinatorial Semi-Bandit Problem](https://mlsanity.com/paper/2509.09933/) (2025) - [Toward Optimal Second-Order Path-Length Guarantee for Adversarial Multi-Armed Bandits](https://mlsanity.com/paper/2608.15996/) (2026) ## Abstract (arXiv) This paper considers the multi-armed bandit (MAB) problem and provides a new best-of-both-worlds (BOBW) algorithm that works nearly optimally in both stochastic and adversarial settings. In stochastic settings, some existing BOBW algorithms achieve tight gap-dependent regret bounds of O(sumi: Deltai>0 fraclog TDeltai) for suboptimality gap Deltai of arm i and time horizon T. As Audibert et al. [2007] have shown, however, that the performance can be improved in stochastic environments with low-variance arms. In fact, they have provided a stochastic MAB algorithm with gap-variance-dependent regret bounds of O(sumi: Deltai>0 (fracσi2Deltai + 1) log T ) for loss variance σi2 of arm i. In this paper, we propose the first BOBW algorithm with gap-variance-dependent bounds, showing that the variance information can be used even in the possibly adversarial environment. Further, the leading constant factor in our gap-variance dependent bound is only (almost) twice the value for the lower bound. Additionally, the proposed algorithm enjoys multiple data-dependent regret bounds in adversarial settings and works well in stochastic settings with adversarial corruptions. The proposed algorithm is based on the follow-the-regularized-leader method and employs adaptive learning rates that depend on the empirical prediction error of the loss, which leads to gap-variance-dependent regret bounds reflecting the variance of the arms.