Generalized Linear Bandits with Memory

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{\mathcal{O}}(T^{3/4})$ regret bound stems from a loose analysis, and we provide a sharpened analysis that recovers a $\tilde{\mathcal{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{\mathcal{O}}\left(\sqrt{mT} + d\sqrt{T} + \sqrt{\kappa}d^{2} m^{1/4} T^{1/4} + \kappa d^{2} \right)$, where $d$ denotes the feature dimension, $m$ the memory length, and $\kappa$ 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.

Many online systems, such as recommender systems, learn by repeatedly choosing what to show a user and observing the response. However, these choices can also change the user’s future responses: showing too many similar items may cause fatigue, while other repeated interactions may make related items more appealing. This means that a system must plan ahead, rather than simply choosing the option that looks best at the moment. We study a bandit-with-memory setting that formalizes this type of decision-making problem. Our first result shows that an existing algorithm can achieve improved statistical efficiency without requiring any additional assumptions. We also extend the previous linear model setting to a generalized linear model setting, and propose an algorithm that performs well both statistically and empirically in this more general setting. We prove that the method can learn almost as efficiently as in standard bandit settings, even when rewards follow nonlinear response patterns and depend on recent history. This suggests that recommendation and decision-making systems can account for short-term memory effects without paying a large statistical cost.