Title: Thompson Sampling for a Fatigue-aware Online Recommendation System,
Abstract: In this paper we consider an online recommendation setting, where a platform
recommends a sequence of items to its users at every time period. The users
respond by selecting one of the items recommended or abandon the platform due
to fatigue from seeing less useful items. Assuming a parametric stochastic
model of user behavior, which captures positional effects of these items as
well as the abandoning behavior of users, the platform's goal is to recommend
sequences of items that are competitive to the single best sequence of items in
hindsight, without knowing the true user model a priori. Naively applying a
stochastic bandit algorithm in this setting leads to an exponential dependence
on the number of items. We propose a new Thompson sampling based algorithm with
expected regret that is polynomial in the number of items in this combinatorial
setting, and performs extremely well in practice. We also show a contextual
version of our solution.