Generalized Linear Bandits with Memory

AI summary

Overview

Research area: Sequential decision-making / bandit theory — specifically non-stationary linear and generalized linear bandits where past actions change future rewards (stat.ML; the paper lists its keywords as Machine Learning, ICML).

Technical level: Advanced. The paper is a theoretical regret-analysis paper; the full argument relies on confidence sets, self-concordance, online mirror descent, eigenvalue telescoping, and elliptical-potential arguments.

One-sentence scope: The paper sharpens the regret guarantee for linear bandits with memory from Õ(T^{3/4}) to Õ(√T) without changing the existing algorithm, then introduces generalized linear bandits with memory and a new block-wise algorithm (GLBM-SCB) whose leading regret term is independent of the link function's curvature.

Paper metadata: arXiv:2608.15848v1 [stat.ML], 16 Aug 2026. Authors: Heesang Ann, Hyunjun Choi, Taehyun Hwang, Younghoon Shin, Haeju Cheong, Min-hwan Oh. Affiliations: Seoul National University (Ann, Choi, Hwang, Shin, Oh) and Shinsegae, Seoul, Republic of Korea (Cheong). Correspondence to minoh@snu.ac.kr. The paper notes equal contribution.

What This Paper Is About

In many recommendation settings, repeatedly showing similar items changes how users respond to later items — a recommendation can cause fatigue (rotting) or reinforce interest (rising). This "memory" effect means the reward of one action depends on actions taken earlier, so a greedy policy that looks optimal now can damage future rewards. A previous framework (clerici2024linear) modeled this for linear rewards and reduced the problem to repeatedly executing a fixed block of actions, but its best known regret was Õ(T^{3/4}). This paper asks whether that rate is fundamental or an artifact of a loose proof, and whether the same idea can be carried over to nonlinear (generalized linear) reward models such as clicks or bounded ratings.

Key Contributions

1. A sharper analysis of OFUL-memory for linear bandits with memory. Without modifying the algorithm, the authors improve the regret guarantee from Õ(√(dm) T^{3/4}) to Õ(√(dmT) + d√T), where T is the horizon, d the feature dimension, and m the memory length. The stated reason is that the earlier analysis treated the actions inside a block as if they were sequentially controlled, producing an estimation error that scaled linearly with block length; viewing the block as a single combinatorial decision (borrowing techniques from combinatorial bandits, jin2021shrinking) removes that dependence.

2. A new model: generalized linear bandits with memory. The linear memory model is extended so the reward mean passes through a known, strictly increasing link function. The authors state this captures memory-induced non-stationarity together with nonlinear reward feedback, such as binary clicks or bounded ratings.

3. The GLBM-SCB algorithm. A block-wise confidence-bound algorithm for generalized linear bandits with memory that estimates the unknown parameter with online mirror descent (OMD) and uses auxiliary estimators to approximate curvature-dependent confidence geometry during block construction. It shrinks the confidence bonus using features of actions already placed in the current block, without needing within-block feedback or parameter updates. It is claimed to be the first such guarantee for action-induced non-stationary generalized linear bandits.

4. Numerical experiments that the authors report as consistent with the theoretical findings (the truncated content does not give datasets, baselines, or numbers).

Main Findings

• Õ(T^{3/4}) was an artifact, not a barrier: The paper states the suboptimal rate came from a mismatch in the existing analysis rather than from memory-induced non-stationarity itself. The previous analysis certified the optimistic parameter in the block-level norm induced by Vτ, but bounded prediction error in the within-block norm induced by V{τ,i-1}, forcing the confidence radius to be enlarged by an amount that scales with block length L; the estimation regret was then bounded as Õ(β L √(dT)).

• Block-as-a-combinatorial-decision removes the L factor: Keeping the confidence radius with respect to the block-level Gram matrix and handling the residual mismatch separately, the first term is controlled by the standard elliptical-potential argument and contributes Õ(β√(dT)), while the second term — the discrepancy between block-level and within-block Gram matrices — is bounded by Õ(βLd) using an eigenvalue telescoping argument from jin2021shrinking. Block length L therefore no longer multiplies the √T term.

• Improved linear regret (Theorem 1, informal): With block length L = ⌊m^{1/2} d^{−1/2} T^{1/2} − m⌋, OFUL-memory achieves Regret_T = Õ(R√(mdT) + √(d max{d, R²} T)), under Assumption 1.

• Rates and the role of α: The paper explains that if the estimation error has the form L^α √T + h(L,T), balancing against the cyclic approximation error O(mT/(m+L)) gives a rate of order O(T^{(1+2α)/(2+2α)} + h(L,T)), so reaching a √T-type rate requires α = 0. The previous analysis effectively had α = 1.

• Generalized linear regret bound: For GLBM-SCB, the abstract reports Õ(√(mT) + d√T + √κ d² m^{1/4} T^{1/4} + κd²), where d is the feature dimension, m the memory length, and κ the curvature parameter of the link function. The leading regret term is independent of the curvature of the link function.

• Oracle greedy fails: Proposition 1 states that for generalized linear bandits with memory, with μ continuous and strictly increasing on the feasible score domain, there exist both rotting and rising instances where the oracle greedy policy incurs linear regret. This mirrors and extends the linear-model result, since myopic maximization of μ(⟨x, A_{t−1}θ*⟩) is equivalent to myopic maximization of the latent score.

• Model structure: The memory matrix is A(x_1, …, x_m) = (Id + Σ{s=1}^{m} x_s xs^⊤)^γ, with γ > 0 for rising (excitation) effects, γ < 0 for rotting (satiation) effects, and γ = 0 recovering the stationary generalized linear bandit. Expected reward satisfies E[y_t | F{t−1}, x_t] = μ(⟨xt, A{t−1}θ*⟩).

• Boundedness implications: Under Assumption 1 (action set closed with ‖x‖₂ ≤ 1, and ‖θ*‖₂ ≤ C_θ for some C_θ > 0), the memory matrix satisfies ‖A{t−1}‖* ≤ (m+1)^{γ_+}, denoted R := (m+1)^{γ_+}, and ‖A_{t−1}θ*‖₂ ≤ R C_θ. In the rotting case γ < 0, R = 1.

• Approximation error: Repeatedly playing an optimal proxy block incurs approximation error of order Θ(mT/(m+L)) up to lower-order boundary terms (given in Appendix H).

• Assumptions on the link: Assumption 2 requires μ twice differentiable with l_μ ≤ μ̇(z) ≤ U_μ on [−RC_θ, RC_θ]; Assumption 3 requires self-concordance |μ̈(z)| ≤ ν · μ̇(z) for all z. The curvature-related nonlinearity parameter is defined as κ := sup over x ∈ X and θ ∈ D of 1/μ̇(x^⊤θ), where D := {θ ∈ R^d : ‖θ‖₂ ≤ RC_θ}.

• Experimental evidence: The paper reports numerical experiments consistent with the theoretical findings; the truncated content does not report experiment sizes, datasets, or numerical values.

Methodology in Plain English

The starting point is a reduction used in earlier work: because rewards depend on recent actions, the learner cannot adapt round by round. Instead it commits to a whole block of m+L actions, executes it, and only then updates its estimate. Regret then splits into two parts — an approximation error from being restricted to cyclic blocks (which shrinks as the block gets longer) and an estimation error from learning a good block (which grows with the block).

The first insight is a reframing. The old analysis measured uncertainty inside a block as though each action in the block were chosen after seeing the previous one — but the block is fixed before any feedback arrives, so it is really one single combinatorial choice. Keeping the confidence radius tied to the pre-block Gram matrix, and bounding the leftover difference between the pre-block and within-block matrices separately using an eigenvalue telescoping argument, stops the block length from multiplying the leading √T error. That is what upgrades the rate to Õ(√T) — with the same off-the-shelf algorithm.

The second part handles nonlinear rewards. In a generalized linear model, how much a new observation teaches you depends not only on the feature direction but also on the local slope (curvature) of the link function — and that slope cannot be measured inside a block because no feedback yet exists. GLBM-SCB works around this in three parts: (i) an OMD estimator updated with a curvature-weighted Gram matrix H; (ii) an information warm-up phase that plays a fixed conservative E-optimal design block until λ_min(V_τ) ≥ L/d, so the curvature-weighted matrix is well conditioned (and because the Vτ are monotone increasing, the condition stays satisfied afterwards); and (iii) after warm-up, a block-safe shrunken confidence bound that combines an action-wise bonus using features of actions already placed in the block with a block-level safety bonus guaranteeing optimism for the whole block. Curvature values that might occur during the block are certified using only the pre-block estimate θ_τ, via the enlarged confidence set C_τ^{(2β)} := {θ ∈ B_d(C_θ) : ‖θ − θ_τ‖{H_τ} ≤ 2β}.

Why This Matters

Impact on research: The paper separates two things that had been conflated — the difficulty caused by memory-induced non-stationarity and the difficulty caused by how uncertainty is bookkept inside a committed block. Showing that the Õ(T^{3/4}) rate was an analysis artifact realigns the linear-with-memory model with the √T rates typical of stationary linear bandits, and the paper claims the first √T-type guarantee for action-induced non-stationary generalized linear bandits. It also gives a reusable design principle (keep the block-level norm, bound the norm mismatch separately) for other settings with delayed feedback and committed action batches.

Real-world applications:

• Recommendation systems where repeated exposure causes fatigue (rotting) or reinforcement (rising), as in the paper's motivating example of repeatedly recommending similar items.
• Binary click or conversion prediction, where the reward is a bounded nonlinear function of a latent preference score — the generalized linear link function case.
• Ratings or other bounded feedback, where the paper notes linear rewards are often too restrictive.
• Settings with feature-level cross-effects, where one action changes the rewards of similar or related future actions (the paper notes finite-arm rotting/rising bandit models do not capture this).

Industry relevance: Ranking and content-recommendation platforms are the natural beneficiaries, since the model's action space is continuous (a possibly infinite action set X ⊂ R^d of feature vectors) rather than a small finite arm set, and it explicitly models how earlier placements shift the preference vector that determines later rewards.

Future Directions

• Tightening the GLBM-SCB bound, especially the curvature terms. The bound includes √κ d² m^{1/4} T^{1/4} and a κd² term; the truncated content does not state whether these are optimal or whether the √κ and d² factors can be reduced.
• Whether the block-level safety bonus is necessary. The shrunken bonus must be paired with a separate safety bonus for optimism over the whole block; the paper does not report whether this can be replaced by a single tighter construction.
• Lower bounds. The paper establishes upper bounds on regret for both the linear and generalized linear memory models; the truncated content does not report matching lower bounds, leaving open whether Õ(√T) is unimprovable in these models.
• Broader memory structures and reward families. Remark 1 states the memory matrix definition is without loss of generality and can be generalized to (A_0 + Σ x_s x_s^⊤)^γ provided ‖(A_0)^γ‖_* ≤ C; whether the analysis and algorithm carry through cleanly for general A_0, and for reward families beyond canonical exponential families, is a natural next question.
• Empirical validation at scale. The paper reports numerical experiments consistent with theory, but the truncated content gives no datasets or benchmark numbers, so how the methods behave on large real recommendation data remains to be seen.

Target Audience

Researchers and graduate students in bandit theory and sequential decision-making; theoreticians working on non-stationary or endogenous bandit models and on generalized linear bandits; and machine-learning practitioners with a strong mathematical background who work on recommendation, ranking, or advertising systems where repeated exposure changes user preferences. Readers need comfort with regret analysis, confidence ellipsoids, self-concordance, and online mirror descent to follow the proofs; the problem motivation and high-level conclusions are accessible with less background.

Authors’ 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.