Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper analyzes the regret bounds for $m$-set adversarial bandits under various utility functions (winner reward, sum of rewards) and feedback mechanisms (winner index, winner reward, sum of rewards). The work establishes information-theoretic lower bounds, revealing that minor variations in the bandit setting significantly alter learning rates compared to standard combinatorial and MNL bandit settings. Experiments validate these theoretical findings on synthetic datasets.
Adversarial bandits with $m$-set choices can suffer drastically slower learning rates than previously thought, with regret scaling quadratically with $m$ in some settings.
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.