# Multiarmed Bandits With Limited Expert Advice

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Jun 2013.

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

- [Online Learning and Bandits with Queried Hints](https://mlsanity.com/paper/2211.02703/) (2022)
- [Trading-Off Payments and Accuracy in Online Classification with Paid Stochastic Experts](https://mlsanity.com/paper/2307.00836/) (2023)
- [Improved Regret Bounds for Bandits with Expert Advice](https://mlsanity.com/paper/2406.16802/) (2024)
- [Group Distributionally Robust Optimization with Flexible Sample Queries](https://mlsanity.com/paper/2505.15212/) (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)
- [Nonstochastic Bandits with Infinitely Many Experts](https://mlsanity.com/paper/2102.05164/) (2021)

## Abstract (arXiv)

We solve the COLT 2013 open problem of citetSCB on minimizing regret in the setting of advice-efficient multiarmed bandits with expert advice. We give an algorithm for the setting of K arms and N experts out of which we are allowed to query and use only M experts' advices in each round, which has a regret bound of tildeObigP√fracminK, M NM T after T rounds. We also prove that any algorithm for this problem must have expected regret at least tildeOmegabigP√fracminK, M NMT, thus showing that our upper bound is nearly tight.