# Minimax Optimal Algorithms for Adversarial Bandit Problem with Multiple Plays

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Nov 2019.

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

- [On the Minimax Regret for Online Learning with Feedback Graphs](https://mlsanity.com/paper/2305.15383/) (2023)
- [Efficient Online-Bandit Strategies for Minimax Learning Problems](https://mlsanity.com/paper/2105.13939/) (2021)
- [Generalized Translation and Scale Invariant Online Algorithm for Adversarial Multi-Armed Bandits](https://mlsanity.com/paper/2109.09212/) (2021)
- [Group Distributionally Robust Optimization with Flexible Sample Queries](https://mlsanity.com/paper/2505.15212/) (2025)
- [Optimal Stochastic Nonconvex Optimization with Bandit Feedback](https://mlsanity.com/paper/2103.16082/) (2021)
- [Near-Linear Time Algorithm with Near-Logarithmic Regret Per Switch for Mixable/Exp-Concave Losses](https://mlsanity.com/paper/2109.13786/) (2021)
- [Natural Hierarchical Cluster Analysis by Nearest Neighbors with Near-Linear Time Complexity](https://mlsanity.com/paper/2203.08027/) (2022)
- [Second Order Regret Bounds Against Generalized Expert Sequences under Partial Bandit Feedback](https://mlsanity.com/paper/2204.06660/) (2022)
- [Optimal Tracking in Prediction with Expert Advice](https://mlsanity.com/paper/2208.03708/) (2022)
- [1D to nD: A Meta Algorithm for Multivariate Global Optimization via Univariate Optimizers](https://mlsanity.com/paper/2209.03246/) (2022)
- [Data Dependent Regret Guarantees Against General Comparators for Full or Bandit Feedback](https://mlsanity.com/paper/2303.06526/) (2023)

## Abstract (arXiv)

We investigate the adversarial bandit problem with multiple plays under semi-bandit feedback. We introduce a highly efficient algorithm that asymptotically achieves the performance of the best switching m-arm strategy with minimax optimal regret bounds. To construct our algorithm, we introduce a new expert advice algorithm for the multiple-play setting. By using our expert advice algorithm, we additionally improve the best-known high-probability bound for the multi-play setting by O(√m). Our results are guaranteed to hold in an individual sequence manner since we have no statistical assumption on the bandit arm gains. Through an extensive set of experiments involving synthetic and real data, we demonstrate significant performance gains achieved by the proposed algorithm with respect to the state-of-the-art algorithms.