PreprintCC BY 4.0arXiv
m-Set Adversarial Bandits with Winner Feedback
Abstract
We show upper and lower bounds on the regret of m-set adversarial bandits for different utilities (winner reward or sum of rewards) and feedback models (winner index, winner reward, sum of rewards, and their combinations). By comparing to standard bounds for combinatorial and MNL bandits, our results reveal how subtle changes in the setting can have a dramatic impact on the learning rates. Our main technical contributions are the information-theoretic lower bounds on the regret. Experiments on synthetic data confirm our theoretical analyses.
Related
- Meta-LinEXP3: Online-within-Online Learning for Adversarial Linear Contextual Bandits
- Nearly Minimax Optimal Regret for Adversarial Linear Bandits with Strong Corruptions
- Gaussian Process Bandits for AI System Optimization with Selectively Verified Feedback
- Bandits with Probing: Optimal Coverage and the Role of Feedback
- Near-Optimal First-Order Regret for Bandits with Feedback Graphs
BibTeX
@misc{cesabianchi2026mset,
title = {{m-Set Adversarial Bandits with Winner Feedback}},
author = {Nicolò Cesa-Bianchi and Matteo Papini},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.10128},
eprint = {2610.10128},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.10128},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - m-Set Adversarial Bandits with Winner Feedback
AU - Nicolò Cesa-Bianchi
AU - Matteo Papini
PY - 2026
DA - 2026/10/07
PB - arXiv
DO - 10.48550/arxiv.2610.10128
UR - https://arxiv.org/abs/2610.10128
AB - We show upper and lower bounds on the regret of m-set adversarial bandits for different utilities (winner reward or sum of rewards) and feedback models (winner index, winner reward, sum of rewards, and their combinations). By comparing to standard bounds for combinatorial and MNL bandits, our results reveal how subtle changes in the setting can have a dramatic impact on the learning rates. Our main technical contributions are the information-theoretic lower bounds on the regret. Experiments on synthetic data confirm our theoretical analyses.
ER -