PaperlayerView exact revision on arXiv

Source-linked AI summary

Generalized Linear Bandits with Memory

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

arXiv:2608.15848v1stat.MLcs.LG

TL;DR

Generalized linear bandits with memory involve rewards shaped by past actions, while existing analyses suffer from block-level and action-wise uncertainty mismatches. The paper uses block-level combinatorial analysis and shrunken confidence bounds to obtain √T-type regret, with a leading term independent of link-function curvature.

  • Problem

    Existing analyses mismatch block-level estimation with within-block uncertainty, while extending memory-bandit guarantees to nonlinear rewards remains more delicate.

  • Method

    The paper treats each action block as one combinatorial decision and uses shrunken confidence bounds with shared block-level and inflated intra-block bonuses.

  • Results

    The analysis recovers a sharper √T-type linear regret bound and gives a generalized-linear guarantee whose leading term is independent of link-function curvature.

  • Takeaways & Limitations

    Memory-induced non-stationarity does not by itself fundamentally increase the statistical complexity of these bandit problems.

  • Takeaways & Limitations

    Extending the analysis to approximate oracles for block optimization remains an important direction for future work.

Abstract

from arXiv · show

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.

1. Introduction

The paper models feature-level, action-induced nonstationarity with memory and shows that the prior linear regret rate was looseness from block-level analysis. It extends this principle to generalized linear bandits with a block-wise confidence algorithm whose leading regret term is independent of link-function curvature.

  • Motivation: Feature-level memory captures how past actions alter rewards for related future actions, beyond finite-arm models tied to the selected arm.The framework models structured cross-effects through a memory matrix that transforms the effective preference parameter.
  • Linear bandits with memory: The prior linear-memory guarantee of eO(T^3/4) is loose because it treats jointly selected block actions as sequentially adaptive decisions.The estimator updates only after block execution, so within-block uncertainty should use the pre-execution information structure.
  • Linear bandits with memory: Without modifying OFUL-memory, the sharper analysis improves the linear regret guarantee from eO(T^3/4) to eO(sqrt(T)).Viewing each block as a single combinatorial decision removes the loose linear dependence on block length and yields tighter block-wise uncertainty bounds.
  • Generalized linear bandits with memory: The generalized linear bandit-with-memory framework combines memory-induced nonstationarity with nonlinear feedback such as binary clicks or bounded ratings.GLBM-SCB uses online mirror descent estimation and auxiliary estimators to approximate curvature-dependent confidence geometry during block construction.
  • Experiments: Numerical experiments support the theoretical findings and illustrate the empirical performance of the proposed methods.

2. Preliminaries

The paper formulates generalized linear bandits with finite memory, where expected rewards depend on current actions transformed by a history-dependent memory matrix. It characterizes rising and rotting effects, establishes regularity assumptions, and explains why greedy policies can incur linear regret.

  • Model: The model selects x_t ∈ X ⊂ R^d and observes stochastic rewards whose conditional mean is parameterized by a generalized linear function of x_t and the history-dependent matrix A_{t−1}.The noise η_t = y_t − μ(⟨x_t, A_{t−1}θ*⟩) has zero conditional mean.
  • Memory effects: γ > 0 produces rising or excitation effects, γ < 0 produces rotting or satiation effects, and γ = 0 recovers the stationary generalized linear bandit model.The memory matrix aggregates previous actions and encodes affected directions through its eigenstructure.
  • Assumptions: The framework assumes bounded actions and parameters, a twice-differentiable link function with l_μ ≤ μ˙(z) ≤ U_μ, self-concordance, and curvature parameter κ.The action set satisfies ∥x∥_2 ≤ 1 and the parameter satisfies ∥θ*∥_2 ≤ C_θ.
  • Assumptions: The memory matrix is uniformly bounded by R := (m + 1)^γ+, with R = 1 in the rotting case γ < 0.This bound controls the effective preference parameter under the boundedness assumption.
  • Motivation: Oracle greedy policies can suffer linear regret in both rotting and rising instances because actions that maximize current reward may damage future reward structure.This motivates restricting policies to cyclic action blocks that localize memory dependence within each block.

3. Main Results

The paper sharpens block-level analysis for linear bandits with memory, recovering a tilde-O(sqrt(T)) rate without modifying OFUL-memory. It then extends the approach to generalized linear rewards with shrunken confidence bounds, achieving a curvature-independent leading term despite memory-induced non-stationarity.

  • Linear bandits with memory: tilde-O(sqrt(T)) regret is achieved for linear bandits with memory by refining within-block uncertainty analysis without modifying OFUL-memory.The improvement removes the previously loose dependence that produced tilde-O(T^3/4).
  • Linear bandits with memory: The combinatorial block viewpoint decouples the leading estimation term from block length L, while eigenvalue telescoping handles residual within-block discrepancies.Actions in a block are selected jointly before feedback, so the block is analyzed as one combinatorial decision rather than adaptively action by action.
  • Generalized linear bandits with memory: Shrunken confidence bonuses exploit within-block information while a safety bonus restores valid optimism at the block level.The algorithm uses the shrunken bonus when sufficient for block-level safety and otherwise falls back to the block-safety bonus.
  • Generalized linear bandits with memory: Approximate block optimization through gradient-based methods remains an important direction because the relevant objective is differentiable.The stated regret analysis currently motivates, but does not extend to, such approximate oracles.
  • Generalized linear bandits with memory: The leading regret term is independent of curvature parameter κ, and the algorithm does not require prior knowledge of κ.The guarantee is presented as a first result for action-induced endogenous non-stationary generalized linear bandits.

4. Experiments

The experiments examine memory-aware optimization, block planning in changing environments, and shrunken-confidence improvements over OFUL-memory. GLBM-SCB outperforms memory-agnostic and greedy baselines in logistic rotting and rising settings, with gaps widening over time.

  • Experimental goals: Experiments test whether memory awareness, block planning, and shrunken-confidence design improve performance across nonlinear and linear reward settings.The study targets three phenomena: memory effects in nonlinear models, planning in rising environments, and improvement over OFUL-memory in linear rewards.
  • Baselines: GLBM-SCB is compared with GLB-OMD, which ignores memory and acts round by round, and Oracle Greedy, which knows θ* and greedily maximizes current expected reward.The linear reward experiment additionally includes OFUL-memory.
  • Logistic rotting: GLBM-SCB consistently outperforms GLB-OMD and Oracle Greedy in the logistic rotting environment, with the cumulative-reward gap widening over time.The result is attributed to optimizing over entire blocks instead of making myopic round-by-round decisions.
  • Logistic rising: In the logistic rising environment, the performance gap is more pronounced because Oracle Greedy does not account for actions’ long-term effects on future rewards.The rising environment demonstrates why planning over blocks matters when actions can improve the future reward landscape.

5. Conclusion … C. Canonical Exponential Family

The paper concludes that memory-induced non-stationarity does not fundamentally increase statistical complexity, while its SCB-based generalized-linear-bandit method achieves a T^1/2-type regret rate. The appendix specifies the canonical exponential-family model and situates the approach among linear, generalized-linear, and combinatorial bandit methods.

  • 5. Conclusion: Memory-induced non-stationarity does not fundamentally increase the problem’s statistical complexity, and the prior Õ(T^3/4) linear-bandit bound reflects an analytical mismatch.The proposed analysis treats each block as a single combinatorial decision.
  • 5. Conclusion: The framework decouples memory length from feature dimension, while efficient approximate UCB oracles remain a stated direction for future work.The paper notes that optimization-error propagation must be quantified to improve computational practicality and support richer action classes.
  • B. Related Work: Linear bandits with memory model rewards as <x_t, A_t−1θ>, where the memory matrix incorporates a finite range of past actions.The memory size m determines the history range, while γ quantifies rotting or rising effects.
  • B. Related Work: Õ(T^3/4) regret from OFUL-Memory is described as suboptimal relative to the best known general lower bound.The cited prior work addresses non-stationarity by converting the problem into a stationary bandit through cyclic approximation.
  • B. Related Work: Generalized linear bandit work includes GLM-UCB, maximum-likelihood methods, and OMD-based estimators, with refined confidence sets of radius O(√d log t).The paper adopts the cited confidence sets and online parameter updates for generalized linear bandits with memory.
  • B. Related Work: Combinatorial-bandit techniques are relevant because both settings select arm sets without updating parameters, while prior within-block strategy updates were analyzed only for linear rewards.Whether that approach extends to generalized linear models had remained open.
  • C. Canonical Exponential Family: The canonical exponential-family specification uses z_t = <x_t, A_t−1θ*> with known scale ϕ, log-partition function ψ, dispersion g(ϕ), and base measure h.It implies E[y_t | F_t−1, x_t] = μ(<x_t, A_t−1θ*>) and Var(y_t | F_t−1, x_t) = g(ϕ) μ˙(<x_t, A_t−1θ*>).

D. Proof of Proposition 1

Under any continuous, strictly increasing link function, Proposition 1 constructs rotting and rising generalized linear bandit instances with memory where oracle greedy incurs linear regret. The proof compares greedy with fixed reference policies whose cumulative rewards exceed greedy by a linear gap.

  • Proposition 1: Proposition 1 establishes that oracle greedy can suffer linear regret in both rotting and rising memory scenarios.The result assumes a continuous, strictly increasing link function on the feasible score domain.
  • Rotting case: In the rotting case, the construction uses d = 2, X = {e1, e2}, m = 1, θ∗ = e1, and γ = −β.The parameter β > 0 is chosen so that µ(2−β) approaches µ(0), while µ(1) > µ(0).
  • Greedy behavior: The proof constructs each instance so oracle greedy repeatedly selects e1 at every round.This behavior is shown by characterizing the first decision and applying induction using strict monotonicity of µ.
  • Rotting case: Alternating between e1 and e2 yields µ(1) + µ(0) every two rounds, creating a positive linear gap over oracle greedy.The proof uses this alternating policy as a fixed reference policy.
  • Rising case: In the rising case, always selecting e2 as a reference policy produces regret Ω(T) against oracle greedy.The reference policy’s later-round reward exceeds the greedy trajectory under the constructed memory dynamics.

E. Proof of Proposition 2

Proposition 2 establishes a pre-block prediction-error bound for candidate blocks when the estimator satisfies a weighted confidence condition. The proof combines Taylor expansion, curvature and monotonicity bounds, and weighted Cauchy–Schwarz.

  • Proposition 2: Proposition 2 bounds pre-block prediction error for any candidate block x and indices i from m + 1 through m + L.The result assumes ∥θτ − θ∗∥Hτ ≤ β and defines bi(x) := Ai(x)⊤xi.
  • Proof of Proposition 2: Taylor’s theorem with integral remainder expands the prediction around zτ,i using the estimation discrepancy h.The proof sets zτ,i := bi(x)⊤θτ and h := bi(x)⊤(θ∗ − θτ).
  • Proof of Proposition 2: Taking absolute values uses nonnegative ˙µ(zτ,i) and the curvature bound |¨µ(z)| ≤ νUµ.These properties produce the intermediate Taylor-based error bound.
  • Proof of Proposition 2: Weighted Cauchy–Schwarz bounds h under the positive-definite matrix Hτ, and substitution completes the Taylor-based prediction-error bound.The proof first uses Hτ ≻ 0 before substituting the resulting inequality.

F. Proof of Theorem 1

The section formally states and proves Theorem 1, establishing improved regret for OFUL-memory under bounded linear rewards and conditionally σ-sub-Gaussian noise. The proof decomposes cumulative regret, controls confidence and elliptical-potential terms, and selects a block length balancing the resulting contributions.

  • Theorem statement: Theorem 1 assumes Assumption 1 and conditionally σ-sub-Gaussian noise η_t := y_t − ⟨x_t, A_{t−1}θ*⟩.The theorem concerns the improved regret of OFUL-memory from Clerici et al. (2024).
  • Theorem statement: The analysis sets λ = max{d, R^2}, with R := (1 + m)max{γ, 0}, and uses confidence-radius parameters β_τ.The displayed confidence-radius formula is truncated in the supplied passage.
  • Proof: The final parameter choice is L = ⌈m^1/2d^−1/2T^1/2⌉ − m and λ = O(max{d, R^2}), yielding the stated regret order.The exact final regret expression is truncated in the supplied passage.
  • Proof: The proof decomposes cumulative regret through the expected reward obtained by playing each block action and the proxy reward definition.This connects the algorithm’s regret to the proxy-regret analysis used in subsequent bounds.
  • Proof: The confidence analysis holds on an event Ω whose probability is bounded using Lemma 5, after which the proof separately controls the first and second terms of the regret bound.The first term uses eigenvalues, matrix ordering, Lemma 7, and the elliptical potential lemma; the second uses Cauchy–Schwarz.

G. Proof of Theorem 2

Theorem 2 gives a formal regret guarantee for GLBM-SCB under Assumptions 1–3, with the proof decomposing regret and combining bounded rewards, proxy optimality, and confidence events. The warm-up stopping rule requires at most ⌈1/α⌉ cycles and has regret order O((m + L)τwarm).

  • Theorem statement: Theorem 2 establishes the formal regret bound for Algorithm 1 under Assumptions 1, 2, and 3.The theorem uses β = O(νRCθ and specifies a block parameter involving ⌊T/(m + L)⌋ − m, although the supplied passage is truncated.
  • Warm-up analysis: ⌈1/α⌉ warm-up cycles suffice to satisfy the stopping rule λmin(Vτ) ≥ L/d; when α = Ω(1), τwarm = O(1).Each warm-up block increases the Gram-matrix minimum eigenvalue by αL/d.
  • Warm-up analysis: O((m + L)τwarm) is the regret order imposed by the warm-up stage.Thus, constant α yields a warm-up contribution that is constant in the number of cycles, up to the stated m + L factor.
  • Proof strategy: The proof decomposes cumulative regret using the expected reward rt = E[yt | Ft−1, xt] and the proxy-reward definition er(x).The decomposition is then related to the optimal block ex of the proxy reward.
  • Proof strategy: Rµ := max{|µ((m + 1)γ+Cθ)|, |µ(−(m + 1)γ+Cθ)|} uniformly bounds the generalized-linear reward.This bound is used to upper-bound OPT(T) and control the initial-exploration contribution.

G.1. Technical lemmas for Theorem 2

The section develops technical lemmas that control estimation error, cumulative shrunken confidence widths, and excess certification for Theorem 2. These results use confidence events, curvature bounds, matrix comparisons, and a warm-start spectral condition.

  • Estimation error decomposition: Lemma 1 decomposes estimation error and establishes |er(x) − r̂τ(x)| ≤ Γsafe under the confidence event and curvature assumptions.The proof bounds the first-order term using confidence and the second-order term using |μ¨(z)| ≤ νUμ, then applies the resulting inequalities.
  • Estimation error decomposition: Lemma 1 also shows that the proxy-optimal block is controlled through the prediction certificate and the excess term ξτ(x) := [Γsafeτ(x) − ΓSCBτ(x)]+.The certificate gives er(x) ≤ r̂τ(x) + Γsafe, while ξτ measures the gap between safe and shrunken confidence widths.
  • Cumulative shrunken widths: Lemma 2 bounds the cumulative shrunken widths γτ,i(xτ) for certified-SCB cycles selected by Algorithm 1 on Ω.Its proof combines definitions involving κ, matrix domination, first- and second-order terms, and eigenvalue bounds for Wτ.
  • Cumulative excess certification: Lemma 3 establishes that cumulative excess certification ξτ cannot be the leading term with respect to T for blocks selected by Algorithm 1.The argument assumes the stated Hτ,i-confidence condition and β definition, then uses comparisons among block matrices and the domination part of Lemma 1.
  • Cumulative excess certification: The H-warm-start stopping rule guarantees λq(Hτwarm+1) ≥ λq(Vτwarm+1)/κ ≥ L/κd for every eigenvalue index q.This spectral lower bound is used to control the subsequent cumulative excess-certification analysis.

H. Approximation rate of proxy reward · I. Auxiliary lemmas

The paper sharpens the cyclic proxy-reward analysis by correcting a divisibility issue and measuring approximation error against cumulative proxy reward, yielding a tighter upper bound with a matching lower-bound result. It also collects concentration, confidence-set, matrix, and eigenvalue lemmas supporting the analysis.

  • H. Approximation rate of proxy reward: The revised analysis corrects the claim that an optimal sequence always contains a length-L block exceeding OPT/T, which fails when T is not divisible by L.For the sequence (2, 1, 2), the optimal average is 5/3 while every length-2 block averages 3/2.
  • H. Approximation rate of proxy reward: The correction explicitly accounts for rewards in the remaining T mod L rounds.This removes the gap caused by incomplete blocks in the cyclic construction.
  • H. Approximation rate of proxy reward: Measuring approximation error as OPT − ẽr(ex), rather than OPT − r̃(ex), removes an unnecessary inequality and sharpens the regret bound.The revised quantity compares optimal cumulative reward directly with cumulative proxy reward.
  • H. Approximation rate of proxy reward: The upper bound gives OPT − T/(m + L)ẽr(ex) ≤ mRµ/(m + L)T + LRµ for cyclic play of a proxy-optimal block.The formulation assumes without loss of generality that T is a multiple of m + L, without changing the regret order.
  • H. Approximation rate of proxy reward: A lower-bound proposition establishes that the preceding approximation bound is tight for some problem instance and proxy-optimal block.The result concerns cumulative proxy reward under cyclic play.
  • I. Auxiliary lemmas: The auxiliary results provide high-probability confidence-set containment for θ∗ under specified step-size and regularization choices.Lemma 4 sets η = 1 + νRCθ and λ = max{14dην²R², 6ηνRCθUµ/g(ϕ)} with probability at least 1 − δ.
  • I. Auxiliary lemmas: Additional lemmas establish ridge-estimator concentration under bounded parameters, conditionally σ-sub-gaussian noise, and bounded l2-norm features.These results hold uniformly over the time horizon with probability at least 1 − δ.
  • I. Auxiliary lemmas: The remaining auxiliary lemmas control sequential design matrices and eigenvalues after positive-semidefinite rank-one updates.They apply to bounded vector sequences and symmetric positive definite matrices.

J. Additional Experimental Details

The experiments use finite-memory environments with shared action sets and parameters within each environment, covering logistic and linear rewards across rising and rotting settings. Additional details specify environment dimensions, initialization, and computational resources.

  • General setup: Experiments use a general memory matrix with an initial positive-semidefinite matrix, while algorithms share the action set and parameter θ* within each environment.The action set consists of finite unit-norm feature vectors in R^d.
  • Reward models: Logistic rewards are Bernoulli with mean μ(⟨x_t, A_{t−1}θ*⟩), using μ(z) = 1/(1 + exp(−z)); linear rewards use the identity link.These define the reward models used in the experiments.
  • Logistic rotting environment: γ = −5, m = 5, and d = 10 define the logistic rotting environment, with 30 unit-sphere arms and θ* selected from the action set.The arms are sampled uniformly from the unit sphere.
  • Logistic rising environment: γ = 1, m = 2, and d = 2 define the logistic rising environment, using the unit ball and non-isotropic A0 = e1e1^T to avoid the trivial Oracle Greedy setting.For each run, ε is sampled uniformly from [0.001, 0.1] and θ* = [√ε, √(1 − ε)]^T.
  • Linear rotting environment: γ = −5, m = 30, and d = 10 define the linear rotting environment, with the unit ball as action set and θ* sampled from it.All experiments ran locally on CPU using a MacBook Air with an Apple M3 chip, 8 CPU cores, and 16GB unified memory.
Loading 2608.15848v1…