mlsanityData to 14 Oct 2026

Nonstationary Generalized Linear Bandits with Discounted Online Mirror Descent

arXiv 2605.25590 ↗First posted 25 May 2026stat.ML cs.LGcited by 0

Not on the map. Why?

Abstract (arXiv)

We study nonstationary generalized linear bandits (GLBs), where the expected reward is modeled through a nonlinear link function with an unknown time-varying parameter. This framework encompasses a broad class of reward models, including linear, Bernoulli, and binomial rewards. Existing approaches are predominantly based on maximum-likelihood estimation (MLE), using sliding-window, restart, or discounting mechanisms to handle nonstationarity. Although these methods achieve statistically efficient regret guarantees, they generally require revisiting past observations at every round, which leads to computation and memory costs that grow with time; moreover, several of them rely on a non-convex projection step. In this paper, we propose DOMD-GLB, a new algorithm for nonstationary GLBs that utilizes discounted online mirror descent (DOMD) for parameter estimation, thereby incurring only O(1) computation and memory costs per round. We prove dynamic regret bounds of order tildeO big(cμ-1/2 d3/4 PT1/4 T3/4big) in drifting environments and tildeObig(cμ-1/3 d2/3 GammaT1/3 T2/3big) in piecewise-stationary environments, where d denotes the feature dimension, T the time horizon, PT the path length, GammaT the number of change points, and cμ a curvature parameter associated with the link function, while substantially improving computational efficiency over prior work. To the best of our knowledge, this is the first algorithm for nonstationary GLBs with per-round computation and memory costs independent of time.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 31 of its 39 references that are in the map. First posted on arXiv 25 May 2026.

Builds on

31 of 39 references.

References · 31

  1. 2021Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approachcited by 98
  2. 2019Weighted Linear Bandits for Non-Stationary Environmentscited by 86
  3. 2018Learning to Optimize under Non-Stationaritycited by 85
  4. 2017Scalable Generalized Linear Bandits: Online Computation and Hashingcited by 64
  5. 2021A Simple Approach for Non-stationary Linear Banditscited by 54
  6. 2022Jointly Efficient and Optimal Algorithms for Logistic Banditscited by 41
  7. 2021Weighted Gaussian Process Bandits for Non-stationary Environmentscited by 30
  8. 2020Self-Concordant Analysis of Generalized Linear Bandits with Forgettingcited by 29
  9. 2024A Unified Confidence Sequence for Generalized Linear Models, with Applications to Banditscited by 29
  10. 2020Algorithms for Non-Stationary Generalized Linear Banditscited by 24
  11. 2020IntelligentPooling: Practical Thompson Sampling for mHealthcited by 24
  12. 2024Generalized Linear Bandits with Limited Adaptivitycited by 22
19 more
  1. 2022Non-Stationary Bandit Learning via Predictive Samplingcited by 21
  2. 2024Nearly Minimax Optimal Regret for Multinomial Logistic Banditcited by 20
  3. 2022An Optimization-based Algorithm for Non-stationary Kernel Bandits without Prior Knowledgecited by 17
  4. 2025Generalized Linear Bandits: Almost Optimal Regret with One-Pass Updatecited by 16
  5. 2025Improved Online Confidence Bounds for Multinomial Logistic Banditscited by 15
  6. 2021Regret Bounds for Generalized Linear Bandits under Parameter Driftcited by 13
  7. 2023Smooth Non-Stationary Banditscited by 13
  8. 2021Learning User Preferences in Non-Stationary Environmentscited by 10
  9. 2024Almost Free: Self-concordance in Natural Exponential Families and an Application to Banditscited by 8
  10. 2025Provably Efficient Online RLHF with One-Pass Reward Modelingcited by 8
  11. 2024Randomized Exploration for Reinforcement Learning with Multinomial Logistic Function Approximationcited by 7
  12. 2023High-Dimensional Dynamic Pricing under Non-Stationarity: Learning and Earning with Change-Point Detectioncited by 5
  13. 2024Is Prior-Free Black-Box Non-Stationary Reinforcement Learning Feasible?cited by 5
  14. 2025Heavy-Tailed Linear Bandits: Huber Regression with One-Pass Updatecited by 5
  15. 2026Revisiting Weighted Strategy for Non-stationary Parametric Bandits and MDPscited by 5
  16. 2024Variance-Dependent Regret Bounds for Non-stationary Linear Banditscited by 2
  17. 2025Combinatorial Reinforcement Learning with Preference Feedbackcited by 2
  18. 2025Preference-based Reinforcement Learning beyond Pairwise Comparisons: Benefits of Multiple Optionscited by 2
  19. 2025Constrained Feedback Learning for Non-Stationary Multi-Armed Banditscited by 1

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2023Revisiting Weighted Strategy for Non-stationary Parametric Bandits
  2. 2026Dynamic Regret for Non-Stationary Linear Bandits via Misspecification Reductions
  3. 2025Generalized Kernelized Bandits: A Novel Self-Normalized Bernstein-Like Dimension-Free Inequality and Regret Bounds
  4. 2026Invariance-Based Dynamic Regret Minimization
  5. 2023Reward Learning as Doubly Nonparametric Bandits: Optimal Design and Scaling Laws
  6. 2026Bellman-Centric Learning: Near-Optimal Regret for Linear Bandits with Memory
  7. 2026Offline-to-Online Learning in Linear Bandits
  8. 2026Offline Local Search for Online Stochastic Bandits