mlsanityData to 7 Oct 2026

Weighted Linear Bandits for Non-Stationary Environments

arXiv 1909.09146 ↗First posted 19 Sep 2019cs.LG stat.MLcited by 84

Not on the map. Why?

Abstract (arXiv)

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 d2/3 BT1/3T2/3, where BT 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.

Key facts. Cited by 84 papers in the map (data through 7 Oct 2026). First posted on arXiv 19 Sep 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2020: 1; 2021: 14; 2022: 17; 2023: 14; 2024: 7; 2025: 9; 2026: 22.

84 papers.

Sort:

By area:

  1. 2021Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approachcited by 98
  2. 2021A Simple Approach for Non-stationary Linear Banditscited by 54
  3. 2022Nearly Optimal Algorithms for Linear Contextual Bandits with Adversarial Corruptionscited by 51
  4. 2021Weighted Gaussian Process Bandits for Non-stationary Environmentscited by 30
  5. 2024Which LLM to Play? Convergence-Aware Online Model Selection with Time-Increasing Banditscited by 26
  6. 2021Distribution-free Contextual Dynamic Pricingcited by 22
  7. 2022Non-Stationary Bandit Learning via Predictive Samplingcited by 21
  8. 2021No-Regret Algorithms for Time-Varying Bayesian Optimizationcited by 19
  9. 2022Stochastic Rising Banditscited by 18
  10. 2022An Optimization-based Algorithm for Non-stationary Kernel Bandits without Prior Knowledgecited by 17
  11. 2021Optimistic Policy Optimization is Provably Efficient in Non-stationary MDPscited by 16
  12. 2020Lipschitzness Is All You Need To Tame Off-policy Generative Adversarial Imitation Learningcited by 15
38 more
  1. 2021Regret Bounds for Generalized Linear Bandits under Parameter Driftcited by 13
  2. 2023Smooth Non-Stationary Banditscited by 13
  3. 2024Right Now, Wrong Then: Non-Stationary Direct Preference Optimization under Preference Driftcited by 12
  4. 2021Stochastic Online Linear Regression: the Forward Algorithm to Replace Ridgecited by 10
  5. 2022Reactive Exploration to Cope with Non-Stationarity in Lifelong Reinforcement Learningcited by 9
  6. 2023A Definition of Non-Stationary Banditscited by 9
  7. 2021Generalized non-stationary banditscited by 8
  8. 2022Non-stationary Bandits and Meta-Learning with a Small Set of Optimal Armscited by 8
  9. 2022ANACONDA: An Improved Dynamic Regret Algorithm for Adaptive Non-Stationary Dueling Banditscited by 8
  10. 2023Dynamic Embedding Size Search with Minimum Regret for Streaming Recommender Systemcited by 7
  11. 2023Linear Bandits with Memory: from Rotting to Risingcited by 5
  12. 2024Causally Abstracted Multi-armed Banditscited by 5
  13. 2025Optimistic Task Inference for Behavior Foundation Modelscited by 5
  14. 2026Revisiting Weighted Strategy for Non-stationary Parametric Bandits and MDPscited by 5
  15. 2021Dynamic Regret Minimization for Control of Non-stationary Linear Dynamical Systemscited by 4
  16. 2022Rotting Infinitely Many-armed Banditscited by 4
  17. 2023Robust Causal Bandits for Linear Modelscited by 4
  18. 2026Learning-to-Defer in Non-Stationary Time Series via Switching State-Space Modelscited by 4
  19. 2022Dynamical Linear Banditscited by 3
  20. 2025Non-Stationary Lipschitz Banditscited by 3
  21. 2026ParetoBandit: Budget-Paced Adaptive Routing for Non-Stationary LLM Servingcited by 3
  22. 2021Dynamic Pricing and Learning under the Bass Modelcited by 2
  23. 2021Reconciling Risk Allocation and Prevalence Estimation in Public Health Using Batched Banditscited by 2
  24. 2022Using Non-Stationary Bandits for Learning in Repeated Cournot Games with Non-Stationary Demandcited by 2
  25. 2022Competing Bandits in Time Varying Matching Marketscited by 2
  26. 2022Hypothesis Transfer in Bandits by Weighted Modelscited by 2
  27. 2023Off-Policy Evaluation for Action-Dependent Non-Stationary Environmentscited by 2
  28. 2024Variance-Dependent Regret Bounds for Non-stationary Linear Banditscited by 2
  29. 2024An Adaptive Approach for Infinitely Many-armed Bandits under Generalized Rotting Constraintscited by 2
  30. 2024Improved Bound for Robust Causal Bandits with Linear Modelscited by 2
  31. 2025Explore-then-Commit for Nonstationary Linear Bandits with Latent Dynamicscited by 2
  32. 2026A single algorithm for both restless and rested rotting banditscited by 2
  33. 2021Periodic-GP: Learning Periodic World with Gaussian Process Banditscited by 1
  34. 2022Representation Learning for Context-Dependent Decision-Makingcited by 1
  35. 2022Adversarial Bandits against Arbitrary Strategiescited by 1
  36. 2023MNL-Bandit in non-stationary environmentscited by 1
  37. 2023Non-stationary Delayed Combinatorial Semi-Bandit with Causally Related Rewardscited by 1
  38. 2025LNUCB-TA: Linear-nonlinear Hybrid Bandit Learning with Temporal Attentioncited by 1

50 most cited of 84 All 84 (JSON)