# Refined Lower Bounds for Adversarial Bandits

arXiv: https://arxiv.org/abs/1605.07416 · HTML: https://mlsanity.com/paper/1605.07416/

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 May 2016.

## Built on by (most cited first, 20 of 20)

- [Achieving Near Instance-Optimality and Minimax-Optimality in Stochastic and Adversarial Linear Bandits Simultaneously](https://mlsanity.com/paper/2102.05858/) (2021)
- [An Efficient Pessimistic-Optimistic Algorithm for Stochastic Linear Bandits with General Constraints](https://mlsanity.com/paper/2102.05295/) (2021)
- [Achieving the Pareto Frontier of Regret Minimization and Best Arm Identification in Multi-Armed Bandits](https://mlsanity.com/paper/2110.08627/) (2021)
- [Pareto Regret Analyses in Multi-objective Multi-armed Bandit](https://mlsanity.com/paper/2212.00884/) (2022)
- [Scale Free Adversarial Multi Armed Bandits](https://mlsanity.com/paper/2106.04700/) (2021)
- [Robust Bandit Learning with Imperfect Context](https://mlsanity.com/paper/2102.05018/) (2021)
- [Near-Optimal Goal-Oriented Reinforcement Learning in Non-Stationary Environments](https://mlsanity.com/paper/2205.13044/) (2022)
- [Adversarial Attacks on Adversarial Bandits](https://mlsanity.com/paper/2301.12595/) (2023)
- [Fast rates for prediction with limited expert advice](https://mlsanity.com/paper/2110.14485/) (2021)
- [Coordinated Attacks against Contextual Bandits: Fundamental Limits and Defense Mechanisms](https://mlsanity.com/paper/2201.12700/) (2022)
- [Slowly Changing Adversarial Bandit Algorithms are Efficient for Discounted MDPs](https://mlsanity.com/paper/2205.09056/) (2022)
- [Constant regret for sequence prediction with limited advice](https://mlsanity.com/paper/2210.02256/) (2022)
- [Information-Theoretic Regret Bounds for Bandits with Fixed Expert Advice](https://mlsanity.com/paper/2303.08102/) (2023)
- [Data-Dependent Regret Bounds for Constrained MABs](https://mlsanity.com/paper/2505.20010/) (2025)
- [Risk level dependent Minimax Quantile lower bounds for Interactive Statistical Decision Making](https://mlsanity.com/paper/2510.05808/) (2025)
- [Multi-Armed Bandits With Best-Action Queries](https://mlsanity.com/paper/2605.08287/) (2026)
- [Hierarchical Causal Bandit](https://mlsanity.com/paper/2103.04215/) (2021)
- [Minimax-optimal trust-aware multi-armed bandits](https://mlsanity.com/paper/2410.03651/) (2024)
- [Online Packet Scheduling with Deadlines and Learning](https://mlsanity.com/paper/2606.00835/) (2026)
- [Leveraging Similarities in Multi-Armed Bandits](https://mlsanity.com/paper/2606.23414/) (2026)

## Abstract (arXiv)

We provide new lower bounds on the regret that must be suffered by adversarial bandit algorithms. The new results show that recent upper bounds that either (a) hold with high-probability or (b) depend on the total lossof the best arm or (c) depend on the quadratic variation of the losses, are close to tight. Besides this we prove two impossibility results. First, the existence of a single arm that is optimal in every round cannot improve the regret in the worst case. Second, the regret cannot scale with the effective range of the losses. In contrast, both results are possible in the full-information setting.