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

Zachary Chase, Shinji Ito, Idan Mehalel
10/31/2025
cs.LGstat.ML

No confident code implementation found for this paper.

Abstract

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 $Θ\left( \sqrt{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.

View on arXivView PDF

Code Implementations

No confident code match yet

We couldn't find an author-owned or strongly-evidenced community implementation for this paper. Any repos shown below are weak matches — verify before relying on them.

No code implementations found yet.

Know of an implementation? Let us know in the comments below!

Similar Papers

Improved Regret Bounds for Bandits with Expert Advice

88% match2024

Information-Theoretic Regret Bounds for Bandits with Fixed Expert Advice

86% match2023

On Interpolating Experts and Multi-Armed Bandits

86% match2023

Near-optimal Per-Action Regret Bounds for Sleeping Bandits

85% match2024

Rising Rested Bandits: Lower Bounds and Efficient Algorithms

85% match2024

A General Recipe for the Analysis of Randomized Multi-Armed Bandit Algorithms

84% match2023

Cite this paper

@article{chase2025tight,
  title  = {A Tight Lower Bound for Non-stochastic Multi-armed Bandits with Expert Advice},
  author = {Zachary Chase and Shinji Ito and Idan Mehalel},
  year   = {2025},
  eprint = {2511.00257},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2511.00257v1}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2511.00257.svg)](https://codeofpaper.com/paper/2511.00257)

Discussion