Nonstationary Generalized Linear Bandits with Discounted Online Mirror Descent

Joongkyu Lee; Min-hwan Oh

stat.MLMay 25, 2026

Nonstationary Generalized Linear Bandits with Discounted Online Mirror Descent

Authors: Joongkyu Lee, Min-hwan Oh

Organizations: Seoul National University

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 $\tilde{O} \big(c_μ^{-1/2} d^{3/4} P_T^{1/4} T^{3/4}\big)$ 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.

Explore similar work

Jul 8, 2026cs.LG

Nonlinear Bandit

In this paper we first study the problem of generalized linear bandit (GLB) under heavy-tailed noise. The characteristics of heavy-tailed distributions are widely observed in real-world applications such as personalized recommendation, financial markets, and medical treatments. Based on the online mirror descent (OMD) method, we propose an algorithm EHM that extends the adaptive Huber loss method (Wang et al., 2025) with one-pass update (

\mathcal{O}(1)

computational complexity with respect to current round

t

and the time horizon

T

), which simultaneously achieves an almost optimal regret of

\widetilde{\mathcal{O}}(T^{\frac{1}{1+ε}})

where

T

is the time horizon. In addition, by utilizing a special property of some link function (Sawarni et al., 2025), our algorithm eliminates the need to know a commonly used parameter. Next, we study the GLB problem under the case when contextual characteristic becomes piecewise constant, and we slightly revised former algorithm to obtain the PGLB-EHM algorithm. After theoretical analysis, we prove that the regret upper bound order stays the same. Furthermore, we look deeper into a special case of nonlinear bandit (NB) and present the NB-EHM algorithm with bisection method and special restriction. Eventually we utilize the affine lifting approach and show that the general NB problem can be applied with NB-EHM to achieve a sublinear regret bound.

Tianshuo Zheng, Ting Wu, Zhi-Hua Zhou +1

Generalized Linear Bandit Heavy-Tailed Noise Loss Function

Ask PDF

Feb 11, 2026cs.LG

A Jointly Efficient and Optimal Algorithm for Heteroskedastic Generalized Linear Bandits with Adversarial Corruptions

We consider the problem of heteroskedastic generalized linear bandits (GLBs) with adversarial corruptions, which subsumes heteroskedastic linear bandits and logistic/Poisson bandits, in the presence of adversarial corruptions. We propose HCW-GLB-OMD, which consists of two components: an online mirror descent (OMD)-based estimator and Hessian-based confidence weights to achieve corruption robustness. This is computationally efficient in that it only requires

{O}(1)

space and time complexity per iteration. Under the self-concordance assumption on the link function, we show a regret bound of

\tilde{O}\left( d \sqrt{\sum_t g(τ_t) \dotμ_{t,\star}} + d^2 g_{\max} κ+ d (g_{\max} + κ) C \right)

, where

\dotμ_{t,\star}

is the slope of

μ

around the optimal arm at time

t

g(τ_t)

's are potentially exogenously time-varying dispersions (e.g.,

g(τ_t) = σ_t^2

for heteroskedastic linear bandits,

g(τ_t) = 1

for Bernoulli and Poisson),

g_{\max} = \max_{t \in [T]} g(τ_t)

is the maximum dispersion, and

C \geq 0

is the total corruption budget of the adversary. We complement this with a lower bound of

\tildeΩ(d \sqrt{\sum_t g(τ_t) \dotμ_{t,\star}} + d C)

, unifying previous problem-specific lower bounds. Thus, our algorithm achieves, up to a

κ

-factor in the corruption term, instance-wise minimax optimality simultaneously across various instances of heteroskedastic GLBs with adversarial corruptions.

Sanghwa Kim, Junghyun Lee, Se-Young Yun

Mirror Descent Adversarial Corruption Adaptive Adversary

Ask PDF

Jul 3, 2026cs.LG

Dynamic Regret for Non-Stationary Linear Bandits via Misspecification Reductions

Many online decision-making problems involve both round-specific feasible actions and drifting reward models: eligible ad impressions, feasible prices, and available treatments can change over time, while user preferences, demand curves, and patient responses may evolve. Motivated by these applications, we study non-stationary linear bandits with round-specific feasible decision sets. Existing methods that obtain the optimal

\widetilde O(T^{2/3}P_T^{1/3})

dependence, where

P_T

is the path length of the reward-parameter sequence, impose an orthogonal-structure assumption on round-specific decision sets, which can be restrictive in contextual applications. We address this gap through a unified misspecification-reduction viewpoint: after partitioning the horizon into blocks, we relate each block's dynamic regret to regret against a fixed-parameter linear bandit benchmark, with the within-block parameter drift entering as bounded misspecification. Restarting algorithms with misspecification-dependent regret guarantees then yields the optimal

T^{2/3}P_T^{1/3}

dynamic-regret dependence for both linear bandits with general compact decision sets and

K

-armed contextual linear bandits.

Zihao Hu, Yuan Yao, Jiheng Zhang +1

Sublinear Regret Non-Stationarity Regret Feasibility

Ask PDF