Nonstationary Generalized Linear Bandits with Discounted Online Mirror Descent
Abstract
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 Õ (cμ−1/2 d3/4 PT1/4 T3/4) in drifting environments and $\tilde{O}\big(c_μ^{-1/3} d^{2/3} Γ_T^{1/3} T^{2/3}\big) $in piecewise-stationary environments, where d denotes the feature dimension, T the time horizon, PT the path length, ΓT 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.
Related
- Block Optimism for Nonstationary Bandits with Latent Linear Dynamics
- The Price of Current-Effect Inference in Nonstationary Multi-Armed Bandits
- Linear Occupancy Homomorphisms for Discounted Markov Decision Processes
- Nearly Linear-Time Follow-the-Perturbed-Leader for Weakly Observable Graph Bandits
- Set Membership Estimation for Stochastic Linear Contextual Bandits
BibTeX
@misc{lee2026nonstationary,
title = {{Nonstationary Generalized Linear Bandits with Discounted Online Mirror Descent}},
author = {Joongkyu Lee and Min-hwan Oh},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2605.25590},
eprint = {2605.25590},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2605.25590},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Nonstationary Generalized Linear Bandits with Discounted Online Mirror Descent
AU - Joongkyu Lee
AU - Min-hwan Oh
PY - 2026
DA - 2026/09/26
PB - arXiv
DO - 10.48550/arxiv.2605.25590
UR - https://arxiv.org/abs/2605.25590
AB - 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 Õ (c_μ^−1/2 d^3/4 P_T^1/4 T^3/4) in drifting environments and $\tilde{O}\big(c_μ^{-1/3} d^{2/3} Γ_T^{1/3} T^{2/3}\big) $in piecewise-stationary environments, where d denotes the feature dimension, T the time horizon, P_T the path length, Γ_T 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.
ER -