Monotone multi-armed bandit allocations


Aleksandrs Slivkins ;
Proceedings of the 24th Annual Conference on Learning Theory, PMLR 19:829-834, 2011.


We present a novel angle for multi-armed bandits (henceforth abbreviated MAB) which follows from the recent work on \emphMAB mechanisms \citepMechMAB-ec09,DevanurK08,Transform-ec10. The new problem is, essentially, about designing MAB algorithms under an additional constraint motivated by their application to MAB mechanisms.This note is self-contained, although some familiarity with MAB is assumed; we refer the reader to \citeCesaBL-book for more background.

Related Material