Multi-Armed Bandits with Unconventional Feedback

Abstract

The multi-armed bandit (MAB) problem is a mathematical formulation of theexploration-exploitation trade-off inherent to reinforcement learning, in which thelearner chooses an action (symblized by an arm) from a set of available actions ina sequence of trials in order to maximize their reward. In the classical MAB prob-lem, the learner receives absolute bandit feedback i.e. it receives as feedback thereward of the arm it selects. In many practical situations however, different kindof feedback is more readily available. In this thesis, we study two of such kinds offeedbacks, namely, relative feedback and corrupt feedback.The main practical motivation behind relative feedback arises from the task ofonline ranker evaluation. This task involves choosing the optimal ranker from a fi-nite set of rankers using only pairwise comparisons, while minimizing the compar-isons between sub-optimal rankers. This is formalized by the MAB problem withrelative feedback, in which the learner selects two arms instead of one and receivesthe preference feedback. We consider the adversarial formulation of this problemwhich circumvents the stationarity assumption over the mean rewards for the arms.We provide a lower bound on the performance measure for any algorithm for thisproblem. We also provide an algorithm called "Relative Exponential-weight algo-rithm for Exploration and Exploitation" with performance guarantees. We present athorough empirical study on several information retrieval datasets that confirm thevalidity of these theoretical results.The motivating theme behind corrupt feedback is that the feedback the learnerreceives is a corrupted form of the corresponding reward of the selected arm. Prac-tically such a feedback is available in the tasks of online advertising, recommendersystems etc. We consider two goals for the MAB problem with corrupt feedback:best arm identification and exploration-exploitation. For both the goals, we providelower bounds on the performance measures for any algorithm. We also providevarious algorithms for these settings. The main contribution of this module is the al-gorithms "KLUCB-CF" and "Thompson Sampling-CF" which asymptotically attainthe best possible performance. We present experimental results to demonstrate theperformance of these algorithms. We also show how this problem setting can beused for the practical application of enforcing differential privacy.