Monotone multi-armed bandit allocations

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.