Multi-Play Combinatorial Semi-Bandit Problem
Shintaro Nakamura, Yuko Kuroki, Wei Chen · 2025
Read Multi-Play Combinatorial Semi-Bandit Problem by Shintaro Nakamura, Yuko Kuroki, Wei Chen (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-09933.txt.
Description
Shintaro Nakamura and 2 co-authors widen a learning model for repeated choices in a 2025 bandit theory paper. In the classic combinatorial semi-bandit, a player picks a set of arms each round and sees feedback from the chosen ones, a pattern behind many optimisation tasks. Restricting picks to yes-or-no choices, though, shuts out problems built on counts and flows, such as transport plans and knapsack loading.
Their multi-play version lets an action assign any nonnegative whole number to each arm, with repeated feedback to match. One Thompson sampling algorithm stays computable even when the action space explodes, and keeps regret growing only logarithmically over time. A second algorithm hedges both worlds, holding the same calm rate when the world is random and a safer rate when an adversary runs it.
Catalog record
| CREATOR | Shintaro Nakamura, Yuko Kuroki, Wei Chen |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 152 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-09933