Generalized Linear Bandits with Memory

Heesang Ann; Hyunjun Choi; Taehyun Hwang; Younghoon Shin; Haeju Cheong; Min-hwan Oh

stat.MLAug 16, 2026

Generalized Linear Bandits with Memory

Authors: Heesang Ann, Hyunjun Choi, Taehyun Hwang, Younghoon Shin, Haeju Cheong, Min-hwan Oh

Organizations: Seoul National University, Seoul, Republic of Korea · Shinsegae, Seoul, Republic of Korea

Abstract

We study generalized linear bandits with memory, an endogenous non-stationary setting in which rewards depend on past actions through a finite memory matrix. Building on prior work for linear models (Clerici et al., 2024), we show that the previously known $\tilde{O}(T^{3/4})$ regret bound stems from a loose analysis, and we provide a sharpened analysis that recovers a $\tilde{O}(\sqrt{T})$ regret rate in the linear case. We then extend this improvement to generalized linear models and propose a block-wise algorithm based on shrunken confidence bounds. Our algorithm achieves a regret bound of $\tilde{O}\left(\sqrt{mT} + d\sqrt{T} + \sqrtκ\, d^{2} m^{1/4} T^{1/4} + κd^{2} \right)$ , where $d$ denotes the feature dimension, $m$ the memory length, and $κ$ a curvature parameter of the link function. This attains a $\sqrt{T}$ -type rate despite nonlinear rewards and memory effects. To the best of our knowledge, this analysis provides a unified treatment of memory-induced non-stationarity and nonlinear link functions, while ensuring that the leading regret term is independent of the curvature of the link function. We conduct numerical experiments that are consistent with our theoretical findings.

Figures & tables

Figure 1: Illustration of how nonstationary preferences are modeled in the bandit with memory setting. The sphere represents the action space, and the red arrow denotes the preference vector $\mathbf{A}\boldsymbol{\theta}^{*}$ . The preference vector is transformed by a memory matrix that depends on previously selected arm features, resulting in different optimal arms at each round. The color gradient visualizes the distribution of expected rewards over actions at each round: actions in darker purple regions yield higher rewards, whereas those in lighter blue regions yield lower rewards.

\mathbf{x}_{\tau}\in\mathop{\mathrm{argmax}}_{\mathbf{x}\in\mathcal{X}^{m+L}}\hat{r}_{\tau}(\mathbf{x})+\max\{\Gamma^{\mathrm{SCB}}_{\tau}(\mathbf{x}),\Gamma^{\mathrm{safe}}_{\tau}(\mathbf{x})\}

Algorithm 1 GLBM-SCB ( G eneralized L inear B andits with M emory- S hrunken C onfidence B ounds)

Figure 2: The purple ellipsoid, centered at

\boldsymbol{\theta}_{\tau}

, illustrates the pre-block confidence region containing

\boldsymbol{\theta}^{*}

. The darker blue ellipsoid around

\boldsymbol{\theta}^{*}

illustrates the concentration region for the within-block estimates. Together, these imply that the relevant parameters are covered by the enlarged ellipsoid

\mathcal{C}_{\tau}^{(2\beta)}

, which allows curvature to be certified without observing within-block feedback.

Panel of Figure 3 — Figure 3: Cumulative rewards in bandits-with-memory environments.

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

\mathbf{x}_{\tau}:=(\mathbf{x}_{\tau,1},\ldots,\mathbf{x}_{\tau,m+L})=\mathop{\mathrm{argmax}}_{\{\mathbf{x}_{\tau,i}\}_{i=1}^{m+L}\subset\mathcal{X}}\sup_{\boldsymbol{\theta}\in\mathcal{C}_{\tau}}\sum_{i=m+1}^{m+L}\langle\mathbf{x}_{\tau,i},\mathbf{A}_{\tau,i-1}\boldsymbol{\theta}\rangle

(5)

Appendix

Algorithm 2 OFUL-Memory ( OM ) ( clerici2024linear )

Explore similar work

Bellman-Centric Learning: Near-Optimal Regret for Linear Bandits with Memory
Oct 5, 2026Jingyuan Liu, Huiwen JiaMulti-Armed Bandits Non-Stationary Bandits
Department of Industrial Engineering and Operations Research, University of California, Berkeley
Nonstationary Generalized Linear Bandits with Discounted Online Mirror Descent
May 25, 2026Joongkyu Lee, Min-hwan OhMulti-Armed Bandits Dynamic Regret Minimization
Seoul National University
Nonlinear Bandit
Jul 8, 2026Tianshuo Zheng, Ting Wu, Zhi-Hua Zhou +1Multi-Armed Bandits Heavy-Tailed Noise
School of Mathematics, Nanjing University, Nanjing, 210093, China · School of Artificial Intelligence, Nanjing University, National Key Laboratory for Novel Software Technology, Nanjing, 210023, China · School of Mathematics and Physics, Xi’an Jiaotong-Liverpool University, Suzhou, 215123, China

Oct 5, 2026J/K move · Enter open · S save

Bellman-Centric Learning: Near-Optimal Regret for Linear Bandits with Memory

Jingyuan Liu, Huiwen Jia

Department of Industrial Engineering and Operations Research, University of California, Berkeley

Multi-Armed Bandits Non-Stationary Bandits Generalized Linear Bandits

Open paper AskPDF arXiv

We study linear bandits with memory, where past actions induce endogenous nonstationarity through an arbitrary known, bounded matrix-valued memory map. To trade off exploration and exploitation while accounting for the memory dynamics, we develop RSM-LinUCB, a Bellman-centric algorithm that learns as in linear bandits and plans as in reinforcement learning. This design admits a novel regret decomposition which separates the memory-induced error from the cumulative reward estimation error along the learner's trajectory. We prove a high-probability regret bound of

\widetilde O\big(dRS(M+1)+σd\sqrt T\big)

, where

T

is the learning horizon,

d

is the parameter dimension,

M

is the memory length,

R

and

S

bound the memory-map operator norm and reward-parameter norm, respectively, and

σ

is the sub-Gaussian noise scale. Our results reveal that the multiplicative memory-horizon coupling in prior bounds is not intrinsic: memory only contributes an additive cost, up to logarithmic factors. We also prove a matching minimax lower bound, establishing near-optimality. We further extend the algorithm to generalized linear rewards, preserving this separation with near-optimal memory and leading statistical dependence. Our algorithms outperform the baselines in numerical experiments on synthetic instances and semi-synthetic KV- and semantic-cache tasks.

Abstract

Explore similar work

Bellman-Centric Learning: Near-Optimal Regret for Linear Bandits with Memory

Nonstationary Generalized Linear Bandits with Discounted Online Mirror Descent

Nonlinear Bandit