Regret bounds reveal effects of feedback in adversarial bandits
m-Set Adversarial Bandits with Winner Feedback
Machine Learning
Summary
This paper studies how well machines can learn to choose sets of options when the outcomes are controlled by an adversary rather than random processes. It looks at how different ways of receiving feedback—like seeing just the winner or the sum of rewards—affect the speed of learning. The authors provide mathematical limits on how much ‘regret’ (or lost opportunity) the learner can accumulate under these scenarios. Their results show that small changes in the feedback design can greatly impact learning efficiency. They confirm their findings with experiments on synthetic data.
What this means in practice
- •For online advertisers: Optimize ad selection algorithms when only limited feedback on user clicks or conversions is available.
- •For revenue management teams: Design pricing or promotion strategies using partial feedback about which product bundles perform best under uncertain demand.
Tested on simulated data.
Authors
Nicolò Cesa-Bianchi, Matteo Papini
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.