# Multi-Play Combinatorial Semi-Bandit Problem

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 18 of its 40 references that are in the map.
- First posted on arXiv 12 Sep 2025.

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

- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Bandits](https://mlsanity.com/paper/1807.07623/) (2018)
- [More Adaptive Algorithms for Adversarial Bandits](https://mlsanity.com/paper/1801.03265/) (2018)
- [Combinatorial Multi-Armed Bandit and Its Extension to Probabilistically Triggered Arms](https://mlsanity.com/paper/1407.8339/) (2014)
- [Thompson Sampling for Combinatorial Semi-Bandits](https://mlsanity.com/paper/1803.04623/) (2018)
- [Combinatorial Multi-Armed Bandit with General Reward Functions](https://mlsanity.com/paper/1610.06603/) (2016)
- [Beating Stochastic and Adversarial Semi-bandits Optimally and Simultaneously](https://mlsanity.com/paper/1901.08779/) (2019)
- [Achieving Near Instance-Optimality and Minimax-Optimality in Stochastic and Adversarial Linear Bandits Simultaneously](https://mlsanity.com/paper/2102.05858/) (2021)
- [Improving Regret Bounds for Combinatorial Semi-Bandits with Probabilistically Triggered Arms and Its Applications](https://mlsanity.com/paper/1703.01610/) (2017)
- [Efficient Learning in Large-Scale Combinatorial Semi-Bandits](https://mlsanity.com/paper/1406.7443/) (2014)
- [Statistical Efficiency of Thompson Sampling for Combinatorial Semi-Bandits](https://mlsanity.com/paper/2006.06613/) (2020)
- [First-order regret bounds for combinatorial semi-bandits](https://mlsanity.com/paper/1502.06354/) (2015)
- [Nearly Optimal Best-of-Both-Worlds Algorithms for Online Learning with Feedback Graphs](https://mlsanity.com/paper/2206.00873/) (2022)
- [Combinatorial Semi-Bandit in the Non-Stationary Environment](https://mlsanity.com/paper/2002.03580/) (2020)
- [Tight Lower Bounds for Combinatorial Multi-Armed Bandits](https://mlsanity.com/paper/2002.05392/) (2020)
- [Best-of-Three-Worlds Linear Bandit Algorithm with Variance-Adaptive Regret Bounds](https://mlsanity.com/paper/2302.12370/) (2023)
- [Adversarially Robust Multi-Armed Bandit Algorithm with Variance-Dependent Regret Bounds](https://mlsanity.com/paper/2206.06810/) (2022)
- [Revisiting the Approximate Carath'eodory Problem via the Frank-Wolfe Algorithm](https://mlsanity.com/paper/1911.04415/) (2019)

## Abstract (arXiv)

In the combinatorial semi-bandit (CSB) problem, a player selects an action from a combinatorial action set and observes feedback from the base arms included in the action. While CSB is widely applicable to combinatorial optimization problems, its restriction to binary decision spaces excludes important cases involving non-negative integer flows or allocations, such as the optimal transport and knapsack problems.To overcome this limitation, we propose the multi-play combinatorial semi-bandit (MP-CSB), where a player can select a non-negative integer action and observe multiple feedbacks from a single arm in each round. We propose two algorithms for the MP-CSB. One is a Thompson-sampling-based algorithm that is computationally feasible even when the action space is exponentially large with respect to the number of arms, and attains O(log T) distribution-dependent regret in the stochastic regime, where T is the time horizon. The other is a best-of-both-worlds algorithm, which achieves O(log T) variance-dependent regret in the stochastic regime and the worst-case tildeOleft( √T right) regret in the adversarial regime. Moreover, its regret in adversarial one is data-dependent, adapting to the cumulative loss of the optimal action, the total quadratic variation, and the path-length of the loss sequence. Finally, we numerically show that the proposed algorithms outperform existing methods in the CSB literature.