Generalized Linear Bandits with Memory

{ "core_finding": "The paper demonstrates that the suboptimal regret bound of \u00tilde{O}(T^{3/4}) in linear bandits with memory is an artifact of loose analysis rather than an intrinsic barrier, and it introduces a block-wise algorithm for generalized linear bandits with memory that achieves a sharpened \u00tilde{O}(\sqrt{T}) regret rate independent of the link function's curvature.", "caveats": "The theoretical bounds assume bounded actions and parameter spaces, and require that the horizon length is a multiple of the block length or that boundary effects remain negligible.", "markdown": "## Research Question and Context\n\nMany real-world sequential decision-making tasks, such as recommendation systems, involve user preferences that evolve based on past interactions. For instance, repeatedly recommending similar items can cause user fatigue, leading to rotting rewards, while other interaction patterns may create rising effects. While prior work has studied such non-stationarity in finite-arm bandits, these models rarely capture cross-effects across structured feature spaces. Recently, linear bandits with memory were introduced to model endogenous non-stationarity via a memory matrix dependent on past actions. However, the existing algorithm achieved a suboptimal regret bound of \u00tilde{O}(T^{3/4}) due to how within-block uncertainty was handled. This paper investigates whether this barrier is intrinsic to memory-induced non-stationarity and how to extend these findings to generalized linear models.\n\n## Approach and Methodology\n\nThe authors first re-examine the linear bandit with memory setting and the OFUL-memory algorithm. They observe that the previous loose regret bound stemmed from treating actions within an execution block as sequentially adaptive decisions, despite the learner committing to the entire block beforehand. By adopting a block-level combinatorial viewpoint—treating each block as a single joint decision—they remove the artificial linear dependence on block length without modifying the original algorithm.\n\nBuilding upon this insight, the authors introduce generalized linear bandits with memory, extending the framework to nonlinear rewards through a link function. They propose a novel block-wise confidence-bound algorithm named GLBM-SCB (Generalized Linear Bandits with Memory via Shrunken Confidence Bounds). This algorithm combines online mirror descent (OMD) estimation with auxiliary estimators to approximate the curvature-dependent confidence geometry during block construction. This allows the algorithm to exploit within-block feature information without requiring feedback or parameter updates inside the block.\n\n## Main Findings\n\nThe sharpened analysis for the linear case improves the regret guarantee from \u00tilde{O}(T^{3/4}) to \u00tilde{O}(\sqrt{T}). For generalized linear bandits with memory, the proposed GLBM-SCB algorithm successfully attains a \u00tilde{O}(\sqrt{T})-type regret bound. Crucially, the leading term of this regret bound is independent of the link function's curvature parameter, providing the first such robust guarantee for action-induced non-stationary generalized linear bandits. Numerical experiments validate these theoretical findings.\n\n## Why It Matters\n\nThis work resolves an open question regarding the tightness of regret bounds in memory-driven bandits and successfully bridges the gap between linear memory models and generalized nonlinear rewards. By establishing a unified block-wise uncertainty control mechanism, it paves the way for efficient reinforcement learning and bandit algorithms in complex environments where user feedback is delayed and historical actions persistently alter future reward distributions.\n\n## Key Terms and Definitions\n\n- Memory matrix — A matrix function of past actions that dictates how previous choices transform the effective preference parameter over time.\n- Endogenous non-stationarity — A setting where reward distributions change dynamically as a direct consequence of the agent's own past actions.\n- Cyclic policy — A policy strategy that repeatedly executes a fixed block of actions over consecutive time horizons to localize long-term memory dependencies.\n- Proxy reward — The cumulative expected reward accumulated over a complete execution block used to approximate and optimize long-term performance.\n- Curvature parameter — A constant quantifying the degree of nonlinearity and local slope variations of the reward link function across the feasible domain." }