# Improved Regret Bounds for Bandits with Expert Advice

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 23 references that are in the map.
- First posted on arXiv 24 Jun 2024.

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

- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Online Learning with Feedback Graphs: Beyond Bandits](https://mlsanity.com/paper/1502.07617/) (2015)
- [Efficient Contextual Bandits in Non-stationary Worlds](https://mlsanity.com/paper/1708.01799/) (2017)
- [Nonstochastic Multi-Armed Bandits with Graph-Structured Feedback](https://mlsanity.com/paper/1409.8428/) (2014)
- [Fighting Bandits with a New Kind of Smoothness](https://mlsanity.com/paper/1512.04152/) (2015)
- [From Bandits to Experts: A Tale of Domination and Independence](https://mlsanity.com/paper/1307.4564/) (2013)
- [The price of bandit information in multiclass online classification](https://mlsanity.com/paper/1302.1043/) (2013)
- [Make the Minority Great Again: First-Order Regret Bound for Contextual Bandits](https://mlsanity.com/paper/1802.03386/) (2018)
- [On the Minimax Regret for Online Learning with Feedback Graphs](https://mlsanity.com/paper/2305.15383/) (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)
- [Information Capacity Regret Bounds for Bandits with Mediator Feedback](https://mlsanity.com/paper/2402.10282/) (2024)

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

- [Infinite-Dimensional Operator/Block Kaczmarz Algorithms: Regret Bounds and λ-Effectiveness](https://mlsanity.com/paper/2511.07604/) (2025)
- [A Tight Lower Bound for Non-stochastic Multi-armed Bandits with Expert Advice](https://mlsanity.com/paper/2511.00257/) (2025)
- [Policy Regret for Embedding Model Routing: Contextual Bandits with Low-Rank Experts](https://mlsanity.com/paper/2606.14929/) (2026)

## Abstract (arXiv)

In this research note, we revisit the bandits with expert advice problem. Under a restricted feedback model, we prove a lower bound of order √K T ln(N/K) for the worst-case regret, where K is the number of actions, N>K the number of experts, and T the time horizon. This matches a previously known upper bound of the same order and improves upon the best available lower bound of √K T (ln N) / (ln K). For the standard feedback model, we prove a new instance-based upper bound that depends on the agreement between the experts and provides a logarithmic improvement compared to prior results.