Generic Exploration and K-armed Voting Bandits

Abstract

We study a stochastic online learning scheme with partial feedback where the utility of de-cisions is only observable through an estima-tion of the environment parameters. We pro-pose a generic pure-exploration algorithm, able to cope with various utility functions from multi-armed bandits settings to duel-ing bandits. The primary application of this setting is to offer a natural generalization of dueling bandits for situations where the envi-ronment parameters reflect the idiosyncratic preferences of a mixed crowd. 1.