# A Tight Lower Bound for Non-stochastic Multi-armed Bandits with Expert Advice

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 15 references that are in the map.
- First posted on arXiv 31 Oct 2025.

## Builds on (most cited first, 6 of 6)

- [The price of bandit information in multiclass online classification](https://mlsanity.com/paper/1302.1043/) (2013)
- [Online Learning with Simple Predictors and a Combinatorial Characterization of Minimax in 0/1 Games](https://mlsanity.com/paper/2102.01646/) (2021)
- [Multiclass Online Learnability under Bandit Feedback](https://mlsanity.com/paper/2308.04620/) (2023)
- [Multiarmed Bandits With Limited Expert Advice](https://mlsanity.com/paper/1306.4653/) (2013)
- [On Interpolating Experts and Multi-Armed Bandits](https://mlsanity.com/paper/2307.07264/) (2023)
- [Improved Regret Bounds for Bandits with Expert Advice](https://mlsanity.com/paper/2406.16802/) (2024)

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

- [Policy Regret for Embedding Model Routing: Contextual Bandits with Low-Rank Experts](https://mlsanity.com/paper/2606.14929/) (2026)

## Abstract (arXiv)

We determine the minimax optimal expected regret in the classic non-stochastic multi-armed bandit with expert advice problem, by proving a lower bound that matches the upper bound of Kale (2014). The two bounds determine the minimax optimal expected regret to be Thetaleft( √T K log (N/K)  right), where K is the number of arms, N is the number of experts, and T is the time horizon.