aiqbench analysis
This paper establishes rigorous information-theoretic lower bounds on regret for $m$-set adversarial bandits, demonstrating how specific feedback mechanisms and utility functions drastically alter learning rates compared to standard combinatorial or MNL models. Theoretical findings are validated through synthetic data experiments, offering critical insights into the fundamental limits of multi-arm bandit algorithms under partial observation settings.
m-Set Adversarial Bandits with Winner Feedback
arXiv:2610.10128v1 Announce Type: new 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.
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.
Machine Learning (cs.LG); Machine Learning (stat.ML)
arXiv:2610.10128 [cs.LG]
(or arXiv:2610.10128v1 [cs.LG] for this version)
https://doi.org/10.48550/arXiv.2610.10128 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 180 words
Related coverage
Online Conformal Abstention Under Adversarial Bandit Feedback
arXiv · Oct 6, 2026
Policy Regret for Embedding Model Routing: Contextual Bandits with Low-Rank Experts
arXiv · Sep 28, 2026
Efficient Adversarial Attacks on High-dimensional Offline Bandits
arXiv · Jun 5, 2026
Nearly Tight Bounds for Cross-Learning Contextual Bandits with Graphical Feedback
arXiv · Jul 28, 2026