Weighted Linear Bandits for Non-Stationary Environments

Abstract

We consider a stochastic linear bandit model in which the available actions correspond to arbitrary context vectors whose associated rewards follow a non-stationary linear regression model. In this setting, the unknown regression parameter is allowed to vary in time. To address this problem, we propose D-LinUCB, a novel optimistic algorithm based on discounted linear regression, where exponential weights are used to smoothly forget the past. This involves studying the deviations of the sequential weighted least-squares estimator under generic assumptions. As a by-product, we obtain novel deviation results that can be used beyond non-stationary environments. We provide theoretical guarantees on the behavior of D-LinUCB in both slowly-varying and abruptly-changing environments. We obtain an upper bound on the dynamic regret that is of order d^{2/3} B\_T^{1/3}T^{2/3}, where B\_T is a measure of non-stationarity (d and T being, respectively, dimension and horizon). This rate is known to be optimal. We also illustrate the empirical performance of D-LinUCB and compare it with recently proposed alternatives in simulated environments.

Cited by in corpus (31)

• Beyond Ads: Sequential Decision-Making Algorithms in Law and Public Policy
• Lipschitzness Is All You Need To Tame Off-policy Generative Adversarial Imitation Learning
• Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approach
• Dynamic Embedding Size Search with Minimum Regret for Streaming Recommender System
• Online Stochastic Optimization with Wasserstein Based Non-stationarity
• Dynamic Regret of Policy Optimization in Non-stationary Environments
• Algorithms for Non-Stationary Generalized Linear Bandits
• A Kernel-Based Approach to Non-Stationary Reinforcement Learning in Metric Spaces
• Combinatorial Semi-Bandit in the Non-Stationary Environment
• Efficient Learning in Non-Stationary Linear Markov Decision Processes
• Targeting for long-term outcomes
• Trading-Off Static and Dynamic Regret in Online Least-Squares and Beyond
• Instance-Wise Minimax-Optimal Algorithms for Logistic Bandits
• Optimistic Policy Optimization is Provably Efficient in Non-stationary MDPs
• Non-Stationary Latent Bandits
• Periodic-GP: Learning Periodic World with Gaussian Process Bandits
• Weighted Gaussian Process Bandits for Non-stationary Environments
• Bandits Under The Influence (Extended Version)
• Regret Bounds for Generalized Linear Bandits under Parameter Drift
• Randomized Exploration for Non-Stationary Stochastic Linear Bandits
• Stochastic Online Linear Regression: the Forward Algorithm to Replace Ridge
• Distribution-free Contextual Dynamic Pricing
• Self-Concordant Analysis of Generalized Linear Bandits with Forgetting
• Multitask Bandit Learning Through Heterogeneous Feedback Aggregation
• When and Whom to Collaborate with in a Changing Environment: A Collaborative Dynamic Bandit Solution
• A Regret bound for Non-stationary Multi-Armed Bandits with Fairness Constraints
• Online Model Selection: a Rested Bandit Formulation
• Online Convex Optimization in Changing Environments and its Application to Resource Allocation
• Unifying Clustered and Non-stationary Bandits
• Quick-Draw Bandits: Quickly Optimizing in Nonstationary Environments with Extremely Many Arms
• Recurrent Neural-Linear Posterior Sampling for Nonstationary Contextual Bandits