# On Interpolating Experts and Multi-Armed Bandits

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 21 references that are in the map.
- First posted on arXiv 14 Jul 2023.

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

- [Online Learning with Feedback Graphs: Beyond Bandits](https://mlsanity.com/paper/1502.07617/) (2015)
- [Nonstochastic Multi-Armed Bandits with Graph-Structured Feedback](https://mlsanity.com/paper/1409.8428/) (2014)
- [Towards Instance Optimal Bounds for Best Arm Identification](https://mlsanity.com/paper/1608.06031/) (2016)
- [A Blackbox Approach to Best of Both Worlds in Bandits and Beyond](https://mlsanity.com/paper/2302.09739/) (2023)
- [Connections Between Mirror Descent, Thompson Sampling and the Information Ratio](https://mlsanity.com/paper/1905.11817/) (2019)
- [A Near-Optimal Best-of-Both-Worlds Algorithm for Online Learning with Feedback Graphs](https://mlsanity.com/paper/2206.00557/) (2022)
- [Understanding Bandits with Graph Feedback](https://mlsanity.com/paper/2105.14260/) (2021)
- [On the Minimax Regret for Online Learning with Feedback Graphs](https://mlsanity.com/paper/2305.15383/) (2023)
- [Online Learning with Feedback Graphs: The True Shape of Regret](https://mlsanity.com/paper/2306.02971/) (2023)
- [Improved Algorithms for Bandit with Graph Feedback via Regret Decomposition](https://mlsanity.com/paper/2205.15076/) (2022)

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

- [Improved Regret Bounds for Bandits with Expert Advice](https://mlsanity.com/paper/2406.16802/) (2024)
- [A Tight Lower Bound for Non-stochastic Multi-armed Bandits with Expert Advice](https://mlsanity.com/paper/2511.00257/) (2025)
- [A Near-optimal, Scalable and Parallelizable Framework for Stochastic Bandits Robust to Adversarial Corruptions and Beyond](https://mlsanity.com/paper/2502.07514/) (2025)
- [On the Problem of Best Arm Retention](https://mlsanity.com/paper/2504.11866/) (2025)

## Abstract (arXiv)

Learning with expert advice and multi-armed bandit are two classic online decision problems which differ on how the information is observed in each round of the game. We study a family of problems interpolating the two. For a vector m=(m1,dots,mK)∈ mathbbNK, an instance of m-MAB indicates that the arms are partitioned into K groups and the i-th group contains mi arms. Once an arm is pulled, the losses of all arms in the same group are observed. We prove tight minimax regret bounds for m-MAB and design an optimal PAC algorithm for its pure exploration version, m-BAI, where the goal is to identify the arm with minimum loss with as few rounds as possible. We show that the minimax regret of m-MAB is Thetaleft(√Tsumk=1Klog (mk+1)right) and the minimum number of pulls for an (ε,0.05)-PAC algorithm of m-BAI is Thetaleft(frac1ε2· sumk=1Klog (mk+1)right). Both our upper bounds and lower bounds for m-MAB can be extended to a more general setting, namely the bandit with graph feedback, in terms of the clique cover and related graph parameters. As consequences, we obtained tight minimax regret bounds for several families of feedback graphs.