Learning Contextual Bandits in a Non-stationary Environment

Abstract

Multi-armed bandit algorithms have become a reference solution for handling the explore/exploit dilemma in recommender systems, and many other important real-world problems, such as display advertisement. However, such algorithms usually assume a stationary reward distribution, which hardly holds in practice as users' preferences are dynamic. This inevitably costs a recommender system consistent suboptimal performance. In this paper, we consider the situation where the underlying distribution of reward remains unchanged over (possibly short) epochs and shifts at unknown time instants. In accordance, we propose a contextual bandit algorithm that detects possible changes of environment based on its reward estimation confidence and updates its arm selection strategy respectively. Rigorous upper regret bound analysis of the proposed algorithm demonstrates its learning effectiveness in such a non-trivial environment. Extensive empirical evaluations on both synthetic and real-world datasets for recommendation confirm its practical utility in a changing environment.

10 pages, 13 figures, To appear on ACM Special Interest Group on Information Retrieval (SIGIR) 2018

References in corpus (2)

• On Upper-Confidence Bound Policies for Non-Stationary Bandit Problems
• Efficient Contextual Bandits in Non-stationary Worlds

Cited by in corpus (19)

• Estimation-Action-Reflection: Towards Deep Interaction Between Conversational and Recommender Systems
• Seamlessly Unifying Attributes and Items: Conversational Recommendation for Cold-Start Users
• Deep reinforcement learning for search, recommendation, and online advertising: a survey
• Weighted Linear Bandits for Non-Stationary Environments
• Dynamic Embedding Size Search with Minimum Regret for Streaming Recommender System
• Algorithms for Non-Stationary Generalized Linear Bandits
• Fair Contextual Multi-Armed Bandits: Theory and Experiments
• Dynamic Causal Bayesian Optimization
• A Linear Bandit for Seasonal Environments
• Non-Stationary Latent Bandits
• Periodic-GP: Learning Periodic World with Gaussian Process Bandits
• Randomized Exploration for Non-Stationary Stochastic Linear Bandits
• Self-Tuning Bandits over Unknown Covariate-Shifts
• On Limited-Memory Subsampling Strategies for Bandits
• When and Whom to Collaborate with in a Changing Environment: A Collaborative Dynamic Bandit Solution
• Contextual-Bandit Based Personalized Recommendation with Time-Varying User Interests
• Non-Stationary Off-Policy Optimization
• Unifying Clustered and Non-stationary Bandits
• Multiscale Non-stationary Stochastic Bandits