Online Sparse Coding with Bandit Feedback

We consider a novel variant of the contextual bandit problem (i.e., the multi-armed bandit with side-information, or context, available to a decision-maker) where the reward associated with each context-based decision may not always be observed ("missing rewards"). This new problem is motivated by certain on-line settings including clinical trial and ad recommendation applications. In order to address the missing-reward setting, we propose to combine the standard contextual bandit approach with an unsupervised learning mechanism, such as, for example, sparse coding. Unlike standard contextual bandit methods, we are able to learn from all contexts, even those with missing rewards, by improving the representation of a context (via dictionary learning); when the reward is available, the standard contextual bandit learning mechanism is used. Promising empirical results are obtained on several real-life datasets