Time-Sensitive Bandit Learning and Satisficing Thompson Sampling
This addresses a limitation in bandit theory for scenarios where near-optimal actions are preferred over costly learning of optimal ones, though it appears incremental as a variation of an existing method.
The paper tackles the problem of bandit learning with time preference, where existing algorithms like Thompson sampling and UCB perform poorly, by proposing satisficing Thompson sampling and establishing a strong discounted regret bound for it.
The literature on bandit learning and regret analysis has focused on contexts where the goal is to converge on an optimal action in a manner that limits exploration costs. One shortcoming imposed by this orientation is that it does not treat time preference in a coherent manner. Time preference plays an important role when the optimal action is costly to learn relative to near-optimal actions. This limitation has not only restricted the relevance of theoretical results but has also influenced the design of algorithms. Indeed, popular approaches such as Thompson sampling and UCB can fare poorly in such situations. In this paper, we consider discounted rather than cumulative regret, where a discount factor encodes time preference. We propose satisficing Thompson sampling -- a variation of Thompson sampling -- and establish a strong discounted regret bound for this new algorithm.